Knapsack Problem(Greedy Method)

Knapsack Problem is also known as rucksack problem.It is a optimization problem. In Knapsack problem Value and Weight is given to collect most amount value with given weight limit that can be collected.

We can have two categories of Knapsack problem:

[1] 0/1 Knapsack problem:

Here items are not divisible.

[2] Fractional Knapsack problem:

Here items are divisible so we can collect parts of item also.

Here we will solve each of the knapsack problem by greedy method meaning taking decisions without thinking of the consequences.

We can solve this problem by mainly three ways:

1. By sorting the given values:
2. By sorting the given weights:
3. By sorting according to the ratio of value by weight:

[1]Sorting according to the given values:

Steps:

1. First sort the given data in descending order according to the value.
2. For greedy method we want maximum possible value of the collected weights so we will sort in descending order with values.
3. Start comparing the given weight with the sorted data and keep collecting items and subtracting the weight of item from given weight until the given weight becomes zero or compared with all weights.
4. Now while comparing if the problem is 0/1 knapsack type and the given weight becomes less than the current item than skip the item and continue but if the problem is of fractional type collect the value according the weight remaining(Multiply W with ratio of value per weight of the current weight).
5. Add the value of collected items.It is our final Profit.

Example:

Values: 4,2,2,1,10 Weights:12,1,2,1,4

W=15

0/1 Knapsack:

1. Sort in descending order: Now values:10,4,2,2,1 Weights:4,12,1,2,1
2. Compare W with first weight: so here 4 is less than W=15 so collect it and subtract the weight 4 from W=15–4=11.collected items:(value=10,weight= 4)
3. same way with second weight but here weight > W so ignore and go to next weight.Next weight is 1 so collect :(10,4),(2,1) and W=10.
4. same way till all weights are compared .Collected items:(10,4),(2,1),(2,2),(1,1) and W=7.
5. Profit=10+2+2+1=15.

Fractional Knapsack:

1. Sort in descending order: Now values:10,4,2,2,1 Weights:4,12,1,2,1
2. Compare W with first weight: so here 4 is less than W=15 so collect it and subtract the weight 4 from W=15–4=11.collected items:(value=10,weight= 4)
3. same way with second weight but here weight > W so take the fractional part of the item and add profit by Multiplying W with ratio of value per weight of the current weight. Value for remaining W = 11*(4/12)=3.67.
4. same way till all weights are compared .Collected items:(10,4),(part of weight 4,12) and W=0.
5. Profit=10+3.67=13.67.

[2]Sorting according to the given Weights:

Steps:

1. First sort the given data in ascending order according to the Weight.
2. For greedy method we want maximum possible value of the collected weights so we will sort in ascending order with weights.
3. Start comparing the given weight with the sorted data and keep collecting items and subtracting the weight of item from given weight until the given weight becomes zero or compared with all weights.
4. Now while comparing if the problem is 0/1 knapsack type and the given weight becomes less than the current item than skip the item and continue but if the problem is of fractional type collect the value according the weight remaining(Multiply W with ratio of value per weight of the current weight).
5. Add the value of collected items.It is our final Profit.

Example:

Values: 4,2,2,1,10 Weights:12,1,2,1,4

W=15

0/1 Knapsack:

1. Sort in ascending order: Now Weights:12,4,2,1,1 values:4,10,2,2,1
2. Compare W with first weight: so here 12 is less than W=15 so collect it and subtract the weight 12 from W=15–12=3.collected items:(value=4,weight= 12).
3. same way with second weight but here weight > W so ignore and go to next weight.Next weight is 2 so collect :(4,12),(2,2) and W=1.
4. same way till all weights are compared or W=0 .Collected items:(4,12),(2,2),(2,1) and W=0.
5. Profit=4+2+2=8.

Fractional Knapsack:

1. Sort in ascending order: Now Weights:12,4,2,1,1 values:4,10,2,2,1
2. Compare W with first weight: so here 12 is less than W=15 so collect it and subtract the weight 12 from W=15–12=3.collected items:(value=4,weight= 12).
3. same way with second weight but here weight > W so take the fractional part of the item and add profit by Multiplying W with ratio of value per weight of the current weight. Value for remaining W = 3*(10/4)=7.5.
4. same way till all weights are compared .Collected items:(4,12),(part of weight 10,4) and W=0.
5. Profit=4+7.5=11.5 .

[3]Sorting according to the given ratio of value by weight:

Steps:

1. First sort the given data in descending order according to the Weight.
2. For greedy method we want maximum possible value of the collected weights so we will sort in descending order with ratio of value by weight.
3. Start comparing the given weight with the sorted data and keep collecting items and subtracting the weight of item from given weight until the given weight becomes zero or compared with all weights.
4. Now while comparing if the problem is 0/1 knapsack type and the given weight becomes less than the current item than skip the item and continue but if the problem is of fractional type collect the value according the weight remaining(Multiply W with ratio of value per weight of the current weight).
5. Add the value of collected items.It is our final Profit.

Example:

Values: 4,2,2,1,10 Weights:12,1,2,1,4

W=15

0/1 Knapsack:

1. Sort in ascending order: Now Weights:4,1,2,1,12 values:10,2,2,1,4 v/w=2.5,2,1,1,0.33.
2. Compare W with first weight: so here 4 is less than W=15 so collect it and subtract the weight 4 from W=15–4=11.collected items:(value=10,weight= 4).
3. same way with second weight but here weight > W so ignore and go to next weight.Next weight is 1 so collect :(10,4),(2,1) and W=10.
4. same way till all weights are compared or W=0 .Collected items:(10,4),(2,1),(2,2),(1,1) and W=7.
5. Profit=10+2+2+1=15.

Fractional Knapsack:

1. Sort in ascending order: Now Weights:4,1,2,1,12 values:10,2,2,1,4 v/w=2.5,2,1,1,0.33.
2. Compare W with first weight: so here 4 is less than W=15 so collect it and subtract the weight 4 from W=15–4=11.collected items:(value=10,weight= 4).
3. same way with weight where weight > W so take the fractional part of the item and add profit by Multiplying W with ratio of value per weight of the current weight. Value for remaining W = 7*(4/12)=2.33.
4. same way till all weights are compared or W=0 .Collected items:(10,4),(2,1),(2,2),(1,1),(part of 4,12)and W=0.
5. Profit=10+2+2+1+2.33=17.33.

Here Our highest profit is 17.33.So we can conclude that sorting according to the ratio of value by weight will give us the best optimal answers.

Resources:

:Wikipedia.

:Book:Fundamentals of algorithms by Brassard and Bratley.

Thank You