Dynamic Programming Algorithm to Solve 0-1 Knapsack Problem

You are given two lists of integers weights and values which have the same length and an integer capacity. weights[i] and values[i] represent the weight and value of the ith item.

Given that you can take at most capacity weights, and that you can only take at most one copy of each item, return the maximum amount of value you can get.

Constraints
n ≤ 250 where n is the length of weights and values
capacity ≤ 250
Example 1
Input
weights = [1, 2, 3]
values = [1, 5, 3]
capacity = 5
Output
8

0/1 Knapsack Problem solved by Dynamic Programming Algorithm

We can use dp[i][j] to represent the maximum value we can get for the first i-items with capacity j in the knapsack. As each item we have two choices, either choose or skip, then we have the following Dynamic Programming equation:

w[i] is the weight for item i, and v[i] is the value we gain if we pick item i.

For more explanation, please see this post: 0/1 Knapsack Problem

C++ Algorithm to solve the 0/1 knapsack problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int knapsack01(vector<int>& weights, vector<int>& values, int capacity) {
    vector<vector<int>> dp(weights.size() + 1, vector<int>(capacity + 1, 0));
    for (int i = 1; i <= weights.size(); ++ i) {
        for (int j = 1; j <= capacity; ++ j) {
            dp[i][j] = dp[i - 1][j];
            if (j >= weights[i - 1]) {
                dp[i][j] = max(dp[i][j], 
                               dp[i - 1][j - weights[i - 1]]
                               + values[i - 1]);
            }
        }
    }
    return dp[weights.size()][capacity];
}

int knapsack01(vector<int>& weights, vector<int>& values, int capacity) {
    vector<vector<int>> dp(weights.size() + 1, vector<int>(capacity + 1, 0));
    for (int i = 1; i <= weights.size(); ++ i) {
        for (int j = 1; j <= capacity; ++ j) {
            dp[i][j] = dp[i - 1][j];
            if (j >= weights[i - 1]) {
                dp[i][j] = max(dp[i][j], 
                               dp[i - 1][j - weights[i - 1]]
                               + values[i - 1]);
            }
        }
    }
    return dp[weights.size()][capacity];
}

Python Algorithm to solve the 0/1 knapsack problem:

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def knapsack01(self, weights, values, capacity):
        sz = len(weights);
        dp = [[0] * (capacity + 1) for _ in range(sz + 1)]
        for i in range(1, sz + 1):
            for j in range(1, capacity + 1):
                dp[i][j] = dp[i - 1][j]
                if j >= weights[i - 1]:
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - weights[i - 1]]
                                   + values[i - 1])
        return dp[sz][capacity]

class Solution:
    def knapsack01(self, weights, values, capacity):
        sz = len(weights);
        dp = [[0] * (capacity + 1) for _ in range(sz + 1)]
        for i in range(1, sz + 1):
            for j in range(1, capacity + 1):
                dp[i][j] = dp[i - 1][j]
                if j >= weights[i - 1]:
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - weights[i - 1]]
                                   + values[i - 1])
        return dp[sz][capacity]

Both implementation have time complexity O(NC) where N is the number of items and C is the capacity of the knapsack. To avoid checking for boundaries of the array, we allocate one more (shift one to the right) for the DP array.

Knapsack problem: Algorithms Series: 0/1 BackPack – Dynamic Programming and BackTracking

See also: Dynamic Programming Algorithm to Solve the Poly Knapsack (Ubounded) Problem

Knapsack Problems

• Teaching Kids Programming - 0/1 Knapsack: Length of the Longest Subsequence That Sums to Target (Recursion+Memoization=Top Down Dynamic Programming)
• Teaching Kids Programming - 0/1 Knapsack Space Optimised Dynamic Programming Algorithm
• Teaching Kids Programming - Using Bottom Up Dynamic Programming Algorithm to Solve 0/1 Knapsack Problem
• Teaching Kids Programming - 0/1 Knapsack Problem via Top Down Dynamic Programming Algorithm
• Teaching Kids Programming - Multiple Strange Coin Flips/Toss Bottom Up Dynamic Programming Algorithm (Knapsack Variant)
• Teaching Kids Programming - Multiple Strange Coin Flips/Toss Top Down Dynamic Programming Algorithm (Knapsack Variant)
• Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Bottom Up Dynamic Programming Algorithm
• Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Top Down Dynamic Programming Algorithm
• Teaching Kids Programming - Brick Layout (Unlimited Knapsack) via Bottom Up Dynamic Programming Algorithm
• Teaching Kids Programming - Brick Layout (Unlimited Knapsack) via Top Down Dynamic Programming Algorithm
• Count Multiset Sum (Knapsacks) by Dynamic Programming Algorithm
• Count Multiset Sum (Knapsacks) by Recursive BackTracking Algorithm
• Dynamic Programming Algorithm to Solve the Poly Knapsack (Ubounded) Problem
• Dynamic Programming Algorithm to Solve 0-1 Knapsack Problem
• Classic Unlimited Knapsack Problem Variant: Coin Change via Dynamic Programming and Depth First Search Algorithm
• Classic Knapsack Problem Variant: Coin Change via Dynamic Programming and Breadth First Search Algorithm
• Complete Knapsack Problem
• 0/1 Knapsack Problem
• Teaching Kids Programming - Combination Sum Up to Target (Unique Numbers) by Dynamic Programming Algorithms
• Algorithms Series: 0/1 BackPack - Dynamic Programming and BackTracking
• Using BackTracking Algorithm to Find the Combination Integer Sum
• Facing Heads Probabilties of Tossing Strange Coins using Dynamic Programming Algorithm
• Partition Equal Subset Sum Algorithms using DFS, Top-Down and Bottom-up DP

–EOF (The Ultimate Computing & Technology Blog) —