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

Answer 1

Solution:

The algorithm is given below:

Algorithm:

1. calculate the profit proportion in every group by px= vx/wx
2. Sort the objects within the groups in terms of their profit value px
3. find the most values px by comparing max(px) of every group
4. now start selecting the most value px from the groups
5. repeat the above step until the knapsack with weight W is full with the items
6. end

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. :)