Prev: Quantiative Science Before BP's cap&trade rip-off
Next: What is the difference between a value judgment and a fact (description vs prescription)
From: Greg on 15 Jul 2010 21:00
Hello:

This is a problem in theoretical computer science and algorithms.
When solving the 0-1 knapsack problem using dynamic programming, how
can you use the resulting table to determine whether the optimal
solution is unique?

The problem is the following: A thief is going to steal some items
and put them in his knapsack, which has a maximum weight capacity of
W, a positive integer. He must select from a finite set of items,
each of which has a positive integer weight and a positive integer
value (in dollars, say). The thief has to determine which collection
of items light enough for him to carry has the maximum total value.

The solution method is described at http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf
.. The thief makes a table indexed by item number i (from 0 to the
total number of items N) and total weight j (from 0 to W). Let c(i,j)
be the number in the ith row and jth column. c(i,j) is the maximum
total value of items chosen from among items #1, 2, ... i whose total
weight is less than or equal to j. The 0 row and 0 column of the
table are of course zero. It is a simple matter to fill in the table
in row-major order. After the table is complete, c(N,W) is the
maximum value of loot the thief can carry away. The completed table
is then used to determine which items the thief should choose.

My question is, how can you use the table to determine whether the
optimal solution is unique? For example, suppose the knapsack
capacity is 5 pounds, and there are four items, with weight/value
pairs (1 lb, $1), (2 lb., $3), (3 lb., $3), (4 lb., $5). The thief
should take either the first and fourth, or the second and third
items, for a total weight of 5 lb. and value of $6.

The solutions which I have read use a deterministic process for
determining which items the thief takes, which gives you one solution
but does not tell whether it is unique.


Greg Spradlin
From: Ray Vickson on 15 Jul 2010 23:54
On Jul 15, 6:00 pm, Greg <gssprad...(a)gmail.com> wrote:
> Hello:
>
> This is a problem in theoretical computer science and algorithms.
> When solving the 0-1 knapsack problem using dynamic programming, how
> can you use the resulting table to determine whether the optimal
> solution is unique?
>
> The problem is the following:  A thief is going to steal some items
> and put them in his knapsack, which has a maximum weight capacity of
> W, a positive integer.  He must select from a finite set of items,
> each of which has a positive integer weight and a positive integer
> value (in dollars, say).  The thief has to determine which collection
> of items light enough for him to carry has the maximum total value.
>
> The solution method is described athttp://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf
> .  

You can extend the method in the link a bit (storing some extra
information) that allows
for determining ALL solutions. In the notation of the link, the
recursion is
V[i,w]= max(V[i-1,w],v_i + V[i-1,w-w_i]) for 0 <= w <= W and 1 <= i <=
n. You choose the first term in max() if x_i = 0 and the second term
if x_i = 1. Non-uniqueness arises if both terms in max() are equal, so
it does not matter (at a particular [i,w] combination) whether or not
you take x_i = 0 or x_i = 1. Note that the optimum is x_i(i,w). By
keeping track of the x_i values (in particular, keeping track of non-
unique values) you can get all optimal policies by backtracking.

R.G. Vickson


> The thief makes a table indexed by item number i (from 0 to the
> total number of items N) and total weight j (from 0 to W).  Let c(i,j)
> be the number in the ith row and jth column.  c(i,j) is the maximum
> total value of items chosen from among items #1, 2, ... i whose total
> weight is less than or equal to j.  The 0 row and 0 column of the
> table are of course zero.  It is a simple matter to fill in the table
> in row-major order.  After the table is complete, c(N,W) is the
> maximum value of loot the thief can carry away.  The completed table
> is then used to determine which items the thief should choose.
>
> My question is, how can you use the table to determine whether the
> optimal solution is unique?  For example, suppose the knapsack
> capacity is 5 pounds, and there are four items, with weight/value
> pairs (1 lb, $1), (2 lb., $3), (3 lb., $3), (4 lb., $5).  The thief
> should take either the first and fourth, or the second and third
> items, for a total weight of 5 lb. and value of $6.
>
> The solutions which I have read use a deterministic process for
> determining which items the thief takes, which gives you one solution
> but does not tell whether it is unique.
>
> Greg Spradlin

From: Greg on 16 Jul 2010 12:04
On Jul 15, 11:54 pm, Ray Vickson <RGVick...(a)shaw.ca> wrote:
> On Jul 15, 6:00 pm, Greg <gssprad...(a)gmail.com> wrote:
>
>
>
> > Hello:
>
> > This is a problem in theoretical computer science and algorithms.
> > When solving the 0-1 knapsack problem using dynamic programming, how
> > can you use the resulting table to determine whether the optimal
> > solution is unique?
>
> > The problem is the following:  A thief is going to steal some items
> > and put them in his knapsack, which has a maximum weight capacity of
> > W, a positive integer.  He must select from a finite set of items,
> > each of which has a positive integer weight and a positive integer
> > value (in dollars, say).  The thief has to determine which collection
> > of items light enough for him to carry has the maximum total value.
>
> > The solution method is described athttp://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf
> > .  
>
> You can extend the method in the link a bit (storing some extra
> information) that allows
> for determining ALL solutions. In the notation of the link, the
> recursion is
> V[i,w]= max(V[i-1,w],v_i + V[i-1,w-w_i]) for 0 <= w <= W and 1 <= i <=
> n. You choose the first term in max() if x_i = 0 and the second term
> if x_i = 1. Non-uniqueness arises if both terms in max() are equal, so
> it does not matter (at a particular [i,w] combination) whether or not
> you take x_i = 0 or x_i = 1. Note that the optimum is x_i(i,w). By
> keeping track of the x_i values (in particular, keeping track of non-
> unique values) you can get all optimal policies by backtracking.
>
> R.G. Vickson
>
> > The thief makes a table indexed by item number i (from 0 to the
> > total number of items N) and total weight j (from 0 to W).  Let c(i,j)
> > be the number in the ith row and jth column.  c(i,j) is the maximum
> > total value of items chosen from among items #1, 2, ... i whose total
> > weight is less than or equal to j.  The 0 row and 0 column of the
> > table are of course zero.  It is a simple matter to fill in the table
> > in row-major order.  After the table is complete, c(N,W) is the
> > maximum value of loot the thief can carry away.  The completed table
> > is then used to determine which items the thief should choose.
>
> > My question is, how can you use the table to determine whether the
> > optimal solution is unique?  For example, suppose the knapsack
> > capacity is 5 pounds, and there are four items, with weight/value
> > pairs (1 lb, $1), (2 lb., $3), (3 lb., $3), (4 lb., $5).  The thief
> > should take either the first and fourth, or the second and third
> > items, for a total weight of 5 lb. and value of $6.
>
> > The solutions which I have read use a deterministic process for
> > determining which items the thief takes, which gives you one solution
> > but does not tell whether it is unique.
>
> > Greg Spradlin
>
>

Thanks a lot. I get it now.

Greg
 | 
Pages: 1
Prev: Quantiative Science Before BP's cap&trade rip-off
Next: What is the difference between a value judgment and a fact (description vs prescription)