A version using /\. and then backtracking to find the combination:
kv =. (] >. [EMAIL PROTECTED] |.!.0 +)&.>/\. @: ((, <@(0 #~ >:))~ <"0)
kw =. [: (] - {~)&.>/\. <@[ ,~ [: |. ] *&.> 2 ~:&.>/\ kv
kx =. 0 -.~ 2 -~/\ >@kw
10 kx 1 2 3 5 6
5 3 2
Henry Rich
> -----Original Message-----
> From: [EMAIL PROTECTED]
> [mailto:[EMAIL PROTECTED] On Behalf Of Henry Rich
> Sent: Saturday, May 05, 2007 1:19 PM
> To: 'Programming forum'
> Subject: RE: [Jprogramming] Knapsack problem?
>
> 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
