Another version of the knapsack problem is to let the set U contain a set of...

Transcribed Image Text:

Another version of the knapsack problem is to let the set U contain a set of types of items, and the objective is to fill the knapsack with any number of items of each type in order to maximize the total value without exceeding the knapsack capacity. Assume that there is an unlimited number of items of each type. More formally, let T = {t₁, t2,..., tn} be a set of n types of items, and C the knapsack capacity. For 1 ≤j ≤n, let s; and v; be, respectively, the size and value of the items of type j. Find a set of nonnegative integers X₁, X2,...,xn such that is maximized, subject to the constraint n XiVi XiSi <C i=1 where x₁, x2,..., Xn are nonnegative integers. Note that x; = 0 means that no item of the jth type is packed in the knapsack. 1) (13 points) Rewrite the dynamic programming formula for this version of the knapsack problem. 2) (12 points) Solve the following instance of this version of the knapsack problem. There are four types of items with sizes 2, 3, 5, and 6 and values 4, 7, 9, and 11, respectively, and the knapsack capacity is 10. Activate Windo Go to Settings to ac Hint: Try to solve part b in order to help you in solving part a. Another version of the knapsack problem is to let the set U contain a set of types of items, and the objective is to fill the knapsack with any number of items of each type in order to maximize the total value without exceeding the knapsack capacity. Assume that there is an unlimited number of items of each type. More formally, let T = {t₁, t2,..., tn} be a set of n types of items, and C the knapsack capacity. For 1 ≤j ≤n, let s; and v; be, respectively, the size and value of the items of type j. Find a set of nonnegative integers X₁, X2,...,xn such that is maximized, subject to the constraint n XiVi XiSi <C i=1 where x₁, x2,..., Xn are nonnegative integers. Note that x; = 0 means that no item of the jth type is packed in the knapsack. 1) (13 points) Rewrite the dynamic programming formula for this version of the knapsack problem. 2) (12 points) Solve the following instance of this version of the knapsack problem. There are four types of items with sizes 2, 3, 5, and 6 and values 4, 7, 9, and 11, respectively, and the knapsack capacity is 10. Activate Windo Go to Settings to ac Hint: Try to solve part b in order to help you in solving part a.

Answer rating: 100% (QA)

Youve provided a problem statement describing an unbounded knapsack problem an... View the full answer