\"Greedy, but Better\": Given a knapsack problem with a weight capacity C, and n

Question

"Greedy, but Better": Given a knapsack problem with a weight capacity C, and nitems, and each item has a weight W[1:n] and monetary value P[1:n]. You have to determine which items to take so that the total weight is C, and the total value (profit) is maximized. In this case we are considering an integer problem, so you can either take an item, or not take an item, you cannot take it fractionally.

If you recall, the greedy algorithm (which orders the items in order of value to weight ratio), does not perform very well. You can make it perform very very poorly. However, a simple fix can make this algorithm only as bad as a ratio of 2 (compared to the best possible solution). Explain how you fix the greedy algorithm.

suject

design and analysis algorithm

Explanation / Answer

If we use greedy algorithm to solve the above problem there will be three possibilities.

Option 1:

Choosing the lightest remaining item in the n items, and take as much of it as can fit the capcacity.

Option 2:

Choosing the most profitable remaining item in the n items, and take as much of it as can fit the capacity.

Option 3:

Choosing the item with the highest price per unit weight (P[i]/W[i]) in the given n items, and take as much of it as can fit the capacity.

If we look at all the three given options option 3 will be the most optimal and best fit to solve this problem. To proof that option 3 is the best greedy approach to solve the above problem we can take a simple example

Let us assume following conditions

i --- 1 2 3 4

P --- 5 9 4 8

W --- 1 3 2 2

Let us assume a capacity C=4 for this problem

P/W --- 5 3 2 4

now if we follow the 3rd approach here

we will take items in this order

Item 1 - Taken full so x[1]=1, x[1]*W[1]=1

Item 4 - Taken full x[4]=1, x[4]*W[4]=2

Item 2 - Taken 1/3 so x[2]=1/3, x[2]*W[2]=1

Now with this approach we have reached our desired capacity C=4 and havn't used the least profitable item 3.

This shows that the greedy approach is best to solve the problem

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.