MathGroup Archive 2010

[Date Index] [Thread Index] [Author Index]

Search the Archive

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
>


  • Prev by Date: Re: Speed Up of Calculations on Large Lists
  • Next by Date: Re: Find the solution of a system of two nonlinear, complicated equations
  • Previous by thread: math lib change in OS X bug + workaround
  • Next by thread: Re: 0/1 knapsack-like minimalization problem and file