Consider the following version of Knapsack. Given are two weight limits W1 and W2, where W1 ≤ W2. Given are also n items (w1, c1),(w2, c2), . . . ,(wn, cn), where wi is the weight and ci the cost of the i-th item. We want to find a subset of these items of the highest cost, where the subset weights 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.)
Consider the following version of Knapsack. Given are two weight limits W1 and W2, where
W1 ≤ W2. Given are also n items (w1, c1),(w2, c2), . . . ,(wn, cn), where wi
is the weight and ci
the cost of the i-th item. We want to find a subset of these items of the highest cost, where
the subset weights at least W1 and at most W2. Give an O(nW2)
(Recall that the cost (respectively weight) of a subset is the sum of the costs (respectively
weights) of the items in the subset.)
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
This a dynamic
by Bartleby ExpertThis a dynamic
by Bartleby Expert
