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
