I didn't know that. The last version on that page seems like a
good candidate for conversion to J. Here I assume that the value v
is the same as the weight w:
kv =. [: > [: (] >. [EMAIL PROTECTED] |.!.0 +)&.>/ ((, <@(0 #~ >:))~ <"0)
10 kv 1 1 5 7 6
0 1 2 2 2 5 6 7 8 9 9
I don't have any good test data for this, but I tried a bunch
of small combinations and it seemed to come up with the right
answers.
The end part ((, <@(0 #~ >:))~ <"0) is just boxing operands for
the insert.
The (] >. [EMAIL PROTECTED] |.!.0 +)&.>/ does the nested loops shown on the
page.
This returns the best weight as {: of the result.
I don't see any easy way to find
the combination of inputs that produces that weight. I suppose
if you used /\. rather than / there might be enough history to
figure out the combination.
Henry Rich
> -----Original Message-----
> From: [EMAIL PROTECTED]
> [mailto:[EMAIL PROTECTED] On Behalf Of John Randall
> Sent: Saturday, May 05, 2007 12:05 PM
> To: Programming forum
> Subject: Re: [Jprogramming] Knapsack problem?
>
> bill lam wrote:
> > I want to burn data files to dvd of 4.5G
> > ?.20#1000
> > 146 755 79 852 854 439 660 257 60 594 246 478 713 318 151
> 92 178 260 90
> > 862
> >
> > how to find the subset of numbers such that their sum is
> nearest but not
> > exceeding 4500?
> >
> >
>
> If you have n integer weights with a total weight W, you can do it by
> dynamic programming in time O(nW). See, for example
>
> http://cgm.cs.mcgill.ca/~msuder/courses/360/lectures/integer-k
> napsack.html
>
> This is usually done recursively with memoization: you may want to
> consider something else in J.
>
> For small n, you can calculate all sums with O(2^n).
>
> Best wishes,
>
> John
>
> ----------------------------------------------------------------------
> For information about J forums see
> http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
