The KNAPSACK problem is defined as follows: You are given a collection of objects. Each object...

Transcribed Image Text:

The KNAPSACK problem is defined as follows: You are given a collection of objects. Each object X has a value X.value and a weight X.weight. You are packing a knapsack and there is a maximum weight W that you can carry. The problem is to choose the objects so that their total weight is at most W, and their total value is as large as possible. In general, if the weights are floating point numbers or large integers, then the problem is believed to be intractable (that is, there is no efficient solution.) However, if all the weights involved are small integers, then there is a solution which is polynomial time in W. Find an efficient dynamic programming solution to the problem, on the assumption that the weights and W are all small positive integers. State the running time of your algorithm as a function of n, the number of objects, and W. Write the algorithm so that the optimal set (not just the optimal value) can be easily recovered, and describe how the set is recovered. Hint: For k=1 to W, for j = 1 to n, find the most valuable subset of the first j objects whose total weight is exactly k. The KNAPSACK problem is defined as follows: You are given a collection of objects. Each object X has a value X.value and a weight X.weight. You are packing a knapsack and there is a maximum weight W that you can carry. The problem is to choose the objects so that their total weight is at most W, and their total value is as large as possible. In general, if the weights are floating point numbers or large integers, then the problem is believed to be intractable (that is, there is no efficient solution.) However, if all the weights involved are small integers, then there is a solution which is polynomial time in W. Find an efficient dynamic programming solution to the problem, on the assumption that the weights and W are all small positive integers. State the running time of your algorithm as a function of n, the number of objects, and W. Write the algorithm so that the optimal set (not just the optimal value) can be easily recovered, and describe how the set is recovered. Hint: For k=1 to W, for j = 1 to n, find the most valuable subset of the first j objects whose total weight is exactly k.

Answer rating: 100% (QA)

Let us assume as follows Let n denotes the number of items W denotes the capacity of the bag w... View the full answer