The Knapsack Problem is a classic optimization problem: given a set of items, each with a weight and a value, determine which items to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
There are two main variants of the problem:
Items cannot be broken down – you either take an item completely or not at all.
This variant requires dynamic programming for an optimal solution.
Items can be divided into smaller pieces – you can take a fraction of an item.
This variant can be solved optimally using a greedy approach.
In the 0/1 Knapsack Problem, each item must be either taken completely or left behind. This problem cannot be solved optimally using a greedy approach and requires dynamic programming.
Generate random items and set a knapsack capacity, then click "Solve with DP" to find the optimal solution.
The dynamic programming approach for the 0/1 Knapsack problem:
function knapsack01(weights, values, capacity):
n = length of weights array
dp = new table of size (n+1) x (capacity+1)
for i from 0 to n:
for w from 0 to capacity:
if i == 0 or w == 0:
dp[i][w] = 0
else if weights[i-1] <= w:
dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w])
else:
dp[i][w] = dp[i-1][w]
return dp[n][capacity]
O(n × W) - Where n is the number of items and W is the capacity
O(n × W) - For the DP table
In the Fractional Knapsack Problem, items can be divided into smaller pieces. This allows for a simpler greedy approach to find the optimal solution.
Generate random items and set a knapsack capacity, then click "Solve with Greedy" to find the optimal solution.
The greedy approach for the Fractional Knapsack problem:
function fractionalKnapsack(items, capacity):
for each item in items:
item.ratio = item.value / item.weight
sort items by ratio descending
remainingCapacity = capacity
totalValue = 0
for each item in items:
if remainingCapacity <= 0:
break
if item.weight <= remainingCapacity:
item.selected = 1
remainingCapacity -= item.weight
totalValue += item.value
else:
fraction = remainingCapacity / item.weight
item.selected = fraction
totalValue += item.value * fraction
remainingCapacity = 0
return totalValue
O(n log n) - Due to sorting items by ratio
O(n) - Only need to store the original items
See how the same set of items is handled using the 0/1 Knapsack (DP) and Fractional Knapsack (Greedy) approaches.