On 7/12/07, John Randall <[EMAIL PROTECTED]> wrote:
> http://cgm.cs.mcgill.ca/~msuder/courses/360/lectures/integer-knapsack.html
If the weight vector is w and the value vector is v, and there are n
items, the page shows that maximizing s=w (+/ .*) v subject to the
constraint s<:W.
Are you sure we are talking about the same page?
I do not see multiplication used in any of the algorithms on that page.
If what you say is true, this would certainly explain some of my
confusion. But... the top of the page says:
Given: A knapsack that can hold a maximum weight of W and a set
of n objects B={b1,...,bn}, each bi with an integer weight wi
and a value vi
To do: Determine the maximum value in objects that will fit
inside the knapsack.
It does not say anything about determining the product of weight and value,
I thought this solved the restaurant problem: w is the cost of each
appetizer, v is the number of each you order, and W is the amount of
money you have. You are trying to find s (and v), and in particular
show that s=W.
I've been thinking of this page as solving the restaurant problem, with
v1=w1, v2=w2, ... vn=wn, and changing the inequality to an equality.
> What I was taking as a general statement about the
> integer knapsack problem was actually a statement
> about the properties of a specific [very bad] algorithm.
I don't see what is so bad about the algorithm described in Step 3 of
the page: it shows that the problem is in P, which I thought was your
original question.
I meant "bad" in terms of execution time.
From the description, the step2 algorithm on that page seems
equivalent to
step2=:4 :0
W=.x
'w v'=.B=.y
m=.w<:W
'w v'=.B=.m#"1 B
if.0=#w do.0 return.end.
>./w+(W-w) step2"0 2]0 2|:1]\."1 B
)
With usage like
15.05 step2 ap,:ap
Or, for it to check all relevant solutions;
15.05 step2 (<.>./W%ap)#"1 ap,:ap
but that would take forever to complete
But
15.05 step2 2#"1 ap,:ap
should at least give 15.05 as its answer.
Later algorithms on this page are more efficient, but none seem
as efficient as my "longwinded" implementation (at least from a J
execution time point of view).
But I can not see a simple way to generalize my "longwinded"
implementation to handle cases where weights and values are
independent. (Extending it to find the objects corresponding to
the maximum suitable sum of their weight is simple, but that
implementation is organized around the idea that equal weights
are interchangable.)
That said, note that my desired result would be the objects
chosen, and the memoizing algorithms do not represent the
time taken to memoize the selected list of objects (just the
available weight).
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
