Horje

CONTINUOUS knapsack problem - Greedy Algorithms - Algorithm
Learn
Algorithm - Greedy Algorithms - Continuous knapsack problem
Continuous knapsack problem

Given items as (value, weight) we need to place them in a knapsack (container) of a capacity k. Note! We can break items to maximize value!

Example input:

values[] = [1, 4, 5, 2, 10]
weights[] = [3, 2, 1, 2, 4]
k = 8

Expected output:

maximumValueOfItemsInK = 20;

Algorithm:

1) Sort values and weights by value/weight.
   values[] = [5, 10, 4, 2, 1]
   weights[] = [1, 4, 2, 2, 3]
2) currentWeight = 0; currentValue = 0;
3) FOR i = 0; currentWeight < k && i < values.length; i++ DO:
       IF k - currentWeight < weights[i] DO
           currentValue = currentValue + values[i];
           currentWeight = currentWeight + weights[i];
       ELSE
           currentValue = currentValue + values[i]*(k - currentWeight)/weights[i]
           currentWeight = currentWeight + weights[i]*(k - currentWeight)/weights[i]
       END_IF
   END_FOR
   PRINT "maximumValueOfItemsInK = " + currentValue;

Remarks

A greedy algorithm is an algorithm in which in each step we choose the most beneficial option in every step without looking into the future. The choice depends only on current profit.

Greedy approach is usually a good approach when each profit can be picked up in every step, so no choice blocks another one.

 
Read Article
https://develop.horje.com/learn/1434/reference

 

Horje