Re: 0/1 knapsack-like minimalization problem and file
- To: mathgroup at smc.vnet.net
- Subject: [mg108788] Re: 0/1 knapsack-like minimalization problem and file
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Wed, 31 Mar 2010 05:28:50 -0500 (EST)
Peter Sisak wrote:
> Given the files in a directory, by what method can I receive the list of
> the files that in size is closest to, but not larger than, an arbitrary
> x value, given in bytes? Each file can be listed at most once. The file
> names and their respective sizes must be read in by Mathematica. (The directory contains files with count of around two-three hundred, thus making a brute force "sum then compare" search of all possible combinations would most probably not finish before the next ice age coming...)
> An extension to the above problem: how to find the lists of files, if there are more than one lists permitted, and the aim is to minimise the total difference between the respective groups and the (identical) x value? (Think archiving data using the least amount of identical-type CDs, or wasting the least amount, and leaving the few odd ones out.)
>
> Any ideas how to pull this? Thanks in advance
> Peter Sisak
>
Once you have the sizes, the code below is a start on the rest.
closestSum[vals_, target_] := Module[
{x, vars, len=Length[vals], obj, constraints, max, best},
vars = Array[x,len];
obj = vars.vals;
constraints = Append[Map[0<=#<=1&, vars], obj<=target];
{max, best} = Maximize[{obj, constraints}, vars, Integers];
{max, vars/.best}
]
Example:
In[24]:= vals = RandomInteger[100, 100]
Out[24]= {55, 71, 25, 66, 73, 28, 82, 70, 45, 81, 7, 71, 45, 38,
10, 66, 58, 71, 3, 2, 88, 46, 95, 83, 81, 5, 56, 30, 35, 2,
86, 53, 22, 69, 97, 20, 45, 17, 90, 39, 64, 36, 85, 87, 19,
73, 93, 43, 1, 82, 85, 35, 65, 9, 6, 22, 75, 26, 62, 85, 59,
10, 41, 35, 83, 47, 75, 22, 26, 29, 15, 16, 65, 94, 96, 31,
12, 14, 70, 20, 89, 12, 76, 6, 81, 1, 23, 49, 41, 76, 15,
59, 13, 22, 38, 30, 36, 37, 4, 61}
In[25]:= closestSum[vals, 4000]
Out[25]= {4000, {0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1,
1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1,
1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
0, 1, 1, 1, 1, 1, 0, 1}}
It will be on the slow side for a list of 200-300 file sizes. I am
looking into that, but I'm not terribly optimistic about finding much
I'll know how to make faster.
Daniel Lichtblau
Wolfram Research