Consider the following more general version of the Knapsack problem. There are p

Question

Consider the following more general version of the Knapsack problem. There are p groups of objects O1, O2, . . . , Op and a knapsack capacity W. Each object x has a weight wx and a value vx. Our goal is to select a subset of objects such that:

• the total weights of selected objects is at most W, • at most one object is selected from any group, and • the total value of the selected objects is maximized

Suppose that n is the total number of objects in all the groups and V is the maximum value of any object, i.e., V = max x is an object vx. Give an O(nW) time algorithm for this general Knapsack problem. Explain the algorithm for this problem.

Hint: Do a dynamic programming with increasing Knapsack capacity

Explanation / Answer

Solution:

The algorithm is given below:

Algorithm:

Running time:

It will take n log n time to sort overall to sort p groups

then max finding will take O(p) time to get the max until the W is full

So the time complexity will be here of O(nW)

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects