Page 1 of 1
Problem 3 Consider the following version of Knapsack. Given are two weight limits W1 and W2, where Wi < W2. Given are al
Posted: Sat Nov 27, 2021 2:33 pm
by answerhappygod
- Problem 3 Consider The Following Version Of Knapsack Given Are Two Weight Limits W1 And W2 Where Wi W2 Given Are Al 1 (126.84 KiB) Viewed 61 times
Problem 3 Consider the following version of Knapsack. Given are two weight limits W1 and W2, where Wi < W2. Given are also n items (W1, C1), (W2, C2), ..., (Wn, Cn), where w; is the weight and Cị the cost of the i-th item. We want to find a subset of these items of the highest cost, with the restriction that the total weight of the chosen items must be at least W1 and at most W2. Give an O(nW2) algorithm for this problem. (Recall that the cost (respectively weight) of a subset is the sum of the costs (respectively weights) of the items in the subset.)