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 >