Step 1: my mathematical knowledge is really basic.
Step 2: my english is basic.
Step 3: I don’t think this is really a “knapsack” problem.
Step 4: I was looking to create the same script you’re describing, so I’ve been reading a bit about the knapsack thing and I wrote a “knapfake” solution. As I understand it, to create the perfect “distributor”, you should check every posible combination of sizes-of-items-near-to-a-max-size. This script will create a list of items, then distribute them in “folders” of a max size, but not extensivelly. Eg:
MAX SIZE = 100 MB
Item 1 = 50 MB
Item 2 = 45 MB
Item 3 = 40 MB
Item 4 = 10 MB
This script would act as follow:
- Item 1 is 50 MB. Fits in the first “folder” (0 MB), so move it there.
- Item 2 is 45 MB. Fits in the first “folder” (50 MB), so move it there.
- Item 3 is 40 MB. Does not fit in the first “folder” (95 MB), so move it to a new folder.
- Item 4 is 10 MB. Does not fit in the first “folder” (95 MB); does fit in the second “folder” (40 MB), so move it there.
This example is not very clear but, basically, it does not check every possible combination of sizes-of-items, but places sequentially every item in the first folder where it can be placed, or moves it to a new folder. Maybe useful if your projects are of a little-variable-size (eg, some of 70MB, lots of 20MB and some more lots of 5MB), then you’d get an acceptable accuracy.
The code:
set maxMB to 695 --> fine for a 700MB CD
set maxbytes to maxMB * (1024 ^ 2)
set inputFolder to (choose folder with prompt "Choose the folder where items to be sub-divided are located currently")
set outputFolder to (choose folder with prompt "Choose the folder where I should locate the items in different folders of max-sixe " & maxMB & " MB")
tell application "Finder" to ¬
{size, name} of items of inputFolder
set mixedList to sortLists from (mixLists(result's item 1, result's item 2)) --> I'm not sure "sortLists" is relevant in this algorithm (???)
set folders to {{}} --> a list with an "empty folder"
set excludedItems to {} --> items shifted from mixedList
set badItems to {} --> items whose size is higher than "maxbytes"
repeat with i from (count mixedList) to 1 by -1
if i is not in excludedItems and i is not in badItems then --> process this item
set itemSize to mixedList's item i's item 1
if itemSize > maxbytes then
set badItems's end to i
else --> try to add item to current "folder"
set itemWasAddedToAnExistingFolder to false
repeat with x from 1 to count folders --> folders's item x is {{size,name},{size,name},...}, Try to add this item to an existing folder
set folderSum to sumFolder(folders's item x)
if (itemSize + folderSum) < maxbytes then --> add item to this "folder"
set end of folders's item x to mixedList's item i
set itemWasAddedToAnExistingFolder to true
exit repeat
end if
end repeat
if not itemWasAddedToAnExistingFolder then
-- display dialog ("foldersum is " & (folderSum / (1024 ^ 2)) & "MB" & return & "size of " & mixedList's item i's item 2 & " is " & (itemSize / (1024 ^ 2)) & return & return & "SO, I'll add this item to a new folder")
set end of folders to {mixedList's item i}
end if
set end of excludedItems to i --> items is now inside a "folder", so exclude it from "mixedList"
end if
end if
end repeat
--> distribute stuff
repeat with i from 1 to count folders --> "folders" is now a list of {{{size, name}, {size, name}}, {{size, name}, {size, name}}}
set currentFolder to folders's item i --> {{size, name}, {size, name}}
--> create a folder with a dummy sequential name, where we will place "files" in this "folder"
set newFolder to ((outputFolder as text) & "dummy" & i)
do shell script "mkdir -p " & quoted form of POSIX path of newFolder
repeat with singleFile in currentFolder
set filepath to alias ((inputFolder as text) & item 2 of singleFile)
--> if this script works fine, uncomment the following line and comment the second-following one (move, instead of duplicate)
-- tell application "Finder" to move filepath to newFolder replacing yes
tell application "Finder" to duplicate filepath to alias newFolder replacing yes
end repeat
end repeat
beep 2
to sumFolder(l) --> l is a list as {{size,name},{size,name}}
set sum to 0
repeat with z in l
set sum to sum + (z's item 1)
end repeat
sum
end sumFolder
to mixLists(a, b)
script foo
property x : a
property y : b
property nl : {}
end script
repeat with i from 1 to count foo's x
set foo's nl's end to {foo's x's item i, foo's y's item i}
end repeat
foo's nl
end mixLists
to sortLists from rList --> credits to Kai Edwards
if rList's length < 2 then return rList
set {l, h, {m, s}} to {{}, {}, rList's {item 1, rest}}
repeat with r in s
if m's item 1 > r's item 1 then
set l's end to r's contents
else
set h's end to r's contents
end if
end repeat
if l's length > 1 then set l to sortLists from l
if h's length > 1 then set h to sortLists from h
l & {m} & h
end sortLists
Hmmm… Talking about “knap”… I’m sure Mr. Knapp would create a much more quick and accurate algorithm :rolleyes:
