WOW! I printed out the knapsack in http://cgms.cs.mcgill.ca/~msunder/courses/360/lectures/integer-knapsack. html and I was actually just studying it and trying to figure out how to use it.
Thank Oleg and Bill. I'll be adding a version of this to my code since my requirement actually specifies multiple garment orders and I have to remove the selected bundles from the list and re-apply the remaining bundles to the next garment quantity. Thanks again. :) -----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Oleg Kobchenko Sent: Wednesday, April 30, 2008 1:35 PM To: Programming forum Subject: RE: [Jprogramming] distribution problem Here's brute-forced knapsack, as Bill correctly suggested. B1=. 20 20 20 25 10 10 8 15 5 5 5 ]B=. /:~ B1 NB. sorted 5 5 5 8 10 10 15 20 20 20 25 N=. ~. B NB. nub Q=. 1+#/.~ B NB. quantities per nub N,:Q 5 8 10 15 20 25 4 2 3 2 4 2 S=. Q #: i.*/Q NB. possible selections ]T=. S +/ . * N NB. totals per selection 0 25 20 45 40 65 60 85 15 40 35 60 55 80 75 100 10 35 30 ... ]G=: /: T NB. graded totals 0 96 48 16 192 144 8 112 288 64 240 2 32 104 208 56 160 ... G{T NB. sort: ({~/:)y is /:~y 0 5 8 10 10 13 15 15 15 18 18 20 20 20 20 23 23 23 25 ... ]P=. 96 I.~ G{T NB. position of cut off 303 ]R=. (P,:20) ];.0 G NB. choice of 20 runner ups 77 151 174 181 253 278 283 350 357 380 15 45 119 142 221 295 318 325 71 94 R{T 98 98 98 98 98 98 98 98 98 98 100 100 100 100 100 100 100 100 103 103 (R{S) +/ . * N 98 98 98 98 98 98 98 98 98 98 100 100 100 100 100 100 100 100 103 103 ":&> (R{S) <@# N NB. actual choices 8 10 15 20 20 25 5 8 20 20 20 25 5 8 10 15 20 20 20 5 8 10 10 20 20 25 5 5 8 15 20 20 25 5 5 8 10 10 20 20 20 5 5 8 10 10 15 20 25 5 5 5 8 15 20 20 20 5 5 5 8 10 20 20 25 5 5 5 8 10 10 15 20 20 15 20 20 20 25 10 10 15 20 20 25 5 10 20 20 20 25 5 10 10 15 20 20 20 5 5 10 15 20 20 25 5 5 5 20 20 20 25 5 5 5 10 15 20 20 20 5 5 5 10 10 20 20 25 8 10 20 20 20 25 8 10 10 15 20 20 20 +/"1 >(M{S) <@# N 98 98 98 98 98 98 98 98 98 98 100 100 100 100 100 100 100 100 103 103 --- On Wed, 4/30/08, Alex Rufon <[EMAIL PROTECTED]> wrote: > Oh. Btw, there is a policy that big quantities in the > bundles should be > used first before the small ones. Hence, in my example, I > primarily used > the 25 and the 20's. ;) > > -----Original Message----- > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] On Behalf Of > Alex Rufon > Sent: Wednesday, April 30, 2008 12:49 PM > To: Programming forum > Subject: [Jprogramming] distribution problem > > This last few days, I've been working on a small module > that calculates > the distribution of bundled material to make a set of > garments. The > first version that I finished today is just doing a > straight forward > distribution and not very optimized (just trying to get a > prototype out > the door). > > To illustrate, let's say that your bundles are: > bundles=. 20 20 20 25 10 10 8 15 5 5 5 > > If the quantity of garments that need to be made from the > bundle is 60. > I just do a progressive sum on the bundles and get all the > values up to > the first qty greater than or equal to the garment quantity > like so: > bundles{.~>:{.I.60<:+/\ bundles > 20 20 20 > > Unfortunately, this would become in-efficient as values as > the bundle > distribution varies, like in this example, the quantity is > 96 > bundles{.~>:{.I.96<:+/\bundles > 20 20 20 25 10 10 > > What I am looking for is a way to find the > "optimum" distribution for a > garment quantity. Like for a garment quantity of 96, a good > distribution > could be > +/ 25 20 20 20 5 8 > 98 > Or a good enough result can be > +/ 25 20 20 20 15 > 100 > > I do have some ideas on how to optimize but all of them > would require a > brute force solution one way or the other. So any > suggestion are highly > appreciated. :) > > Thanks. > > r/Alex > ---------------------------------------------------------------------- > For information about J forums see > http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- > For information about J forums see > http://www.jsoftware.com/forums.htm ________________________________________________________________________ ____________ Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
