Re: 0/1 knapsack-like minimalization problem and file
- To: mathgroup at smc.vnet.net
- Subject: [mg108825] Re: 0/1 knapsack-like minimalization problem and file
- From: ADL <alberto.dilullo at tiscali.it>
- Date: Fri, 2 Apr 2010 05:19:58 -0500 (EST)
- References: <hov844$95u$1@smc.vnet.net>
Peter,
since the methods proposed so far in the discussion turn out not to be
really rigorous in finding the best sublist, I put together another
algorithm which, at least, can run in a limited amount of time.
Below the listing:
ClearAll[bestList];
bestList[uvals_,max_]:=
Module[{newlist,totali,lista,accum,run,num,best,res},
newlist=RandomSample[uvals,Length[uvals]];
totali=Table[
lista=Drop[newlist,i];
accum=Accumulate[lista];
run=TakeWhile[accum,#<=max&];
num[i]=Length[run];
If[num[i]>0,
Last@run,
-1
],
{i,Length[uvals]-1}
];
best=Last@Last@Position[totali,First@Nearest[totali,max]];
res=Take[Drop[newlist,best], num[best]];
{Total@res,res}
];
targetdir = "c:\\aaa\\bbb";
SetDirectory[targetdir];
vals = Map[FileByteCount, FileNames[]];
vals//Length
Out[]= 765
Timing[
result = Last@Sort@Table[bestList[vals,100000000], {200}];
result[[1]]->Sort[result[[2]]]
]
{40.3260000000001,
99999958-
>{1880990,2324083,3033088,3129142,3384605,3720583,3803460,3858972,3991714,4=
118528,4215711,4357700,4382912,4434389,4439762,4774491,5139354,6095644,6532=
024,6942890,7604593,7835323}}
In 40 seconds, a good solution has been found. By changing the number
of attempts (200 in the example above), a shorter time or a better
solution can be achieved. The algorithm can also be instructed to stop
in a given amount of time, thus adapting itself to external
constraints.
With 20 attempts:
Timing[
result=Last@Sort@Table[bestList[vals,100000000], {20}];
result[[1]]->Sort[result[[2]]]
]
{3.80700000000004,
99999778-
>{2554731,3161720,3286912,3581198,3731622,3748762,4082398,4129268,4170725,4=
319282,4326098,4550629,4638840,4931962,5216256,5428975,5580682,6348084,6641=
491,7404767,8165376}}
Note that I could not wait to see the end of closestSum3 in this
example.
ADL
On 31 Mar, 12:28, Peter Sisak <p-ku... at hotmail.com> wrote:
> Hello,
>
> Yes, I think this will be it, in the end. It works very fine and usab=
le. I used a little tweaking myself (so as to prevent having to type in lis=
ts of that length), and used a list sort as a final step so as to facilitat=
e selection in commonly used file manager programs without having to scroll=
up and down too much. For educational purposes, here's the entire code:
>
> targetdir = "A:\bbb\cc"
> SetDirectory[targetdir]
> vals = Map[FileByteCount, FileNames[]]
> closestSum3[vals_, target_, maxiters_: 100, sp_: Automatic,
> cp_: Automatic] :=
> Module[{x, vars, len = Length[vals], obj, constraints, max, best},
> vars = Array[x, len]; obj = vars.vals;
> constraints =
> Join[Map[0 <= # <= 1 &, vars], {obj <= target,
> Element[vars, Integers]}]; {max, best} =
> NMaximize[{obj, constraints}, vars,
> Method -> {"DifferentialEvolution", SearchPoints -> sp,
> "CrossProbability" -> cp}, MaxIterations -> maxiters]; {max,
> vars /. best}]
> Sort[
> Select[(vals (closestSum3[vals, 8547993600, 40, 200, 1/
> 10])[[2]]), #> 0 &], Greater]
> Total[%]
>
> The number of iteration steps was downed to 40, it still produced very go=
od (not to mention fast) results even at that setting. The Total[] was adde=
d so as to permit quick modification of the target value, should the select=
ed files in the end not fit on the desired media after all (in effect, all =
media "waste" space with the used file systems and due to storage block siz=
es.)
> I wish to express my gratitude for your help, and also wish everyone =
who needs the above-written code to use it for whatever he likes and have g=
ood use of it. Of course, if there be further improvements or other approac=
hes to the code and the original problem, I'm more than ready to test those=
too.
>
> Regards
> Peter Sisak
>