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 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
