Continuous knapsack problem
suggest changeGiven 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;
Found a mistake? Have a question or improvement idea?
Let me know.
Table Of Contents