How to 0/1 Knapsack Problem using Memoization in Python and C++

What is the 0/1 Knapsack Problem?

Suppose we have a list of weights and corresponding values for n items. We have a knapsack that can carry items up to a specific maximum weight, known as the capacity of the knapsack. We want to maximize the sum of values of the items in our knapsack while ensuring that the sum of the weights of the items remains less than or equal to the knapsack’s capacity.

If all the combinations exceed the given knapsack’s capacity, then return 0.

Note: The 0/1 in the name refers to the fact that while adding items to the knapsack, we either add the complete item or don’t add it at all. Moreover, we can’t add an item again that is already in the knapsack.

Example

Let’s say we have a knapsack capacity of 40 and a list of items with weights and values as follows:

Though all of the combinations described above are valid, we need to select the one with the maximum value. Therefore, we will select item 1 and item 3 with weights 10 and 30, respectively, as they give us the maximum value of 70.

What is memoization?

Memoization is a technique to overcome the problem of calculating redundant solutions over and over again by storing them in a table.

How to solve the 0/1 knapsack problem using memoization

The basic idea for solving the 0/1 knapsack problem is to define a recursive function that accepts the capacity of the knapsack, weights of the items, values of the items, and a table to store the solutions to the subproblems as input.

The table maintains the information about the values of items if they are included in the knapsack. The result of including an item with a change in remaining capacity is stored in the table. Later, when we have to re-evaluate the inclusion of that item, it can be easily looked up from the table in $O(1)$ instead of recalculating that subproblem.

How to solve 0/1 knapsack problem using memoization in C++

Let's implement the code for solving the 0/1 knapsack problem in C++.

#include <iostream>
#include <vector>
#include <iomanip>
int FindKnapsackRec(int capacity, std::vector<int> &weights, std::vector<int> &values, int n, std::vector<std::vector<int>> &dp) {
    // Base case
    if (n == 0 || capacity == 0)
        return 0;
    // If we have solved it earlier, then return the result from memory
    if (dp[n][capacity] != -1)
        return dp[n][capacity];
    // Otherwise, we solve it for the new combination and save the results in the memory
    if (weights[n - 1] <= capacity) {
        dp[n][capacity] = std::max(
            values[n - 1] + FindKnapsackRec(capacity - weights[n - 1], weights, values, n - 1, dp),
            FindKnapsackRec(capacity, weights, values, n - 1, dp));
        return dp[n][capacity];
    }
    dp[n][capacity] = FindKnapsackRec(capacity, weights, values, n - 1, dp);
    return dp[n][capacity];
}
int FindKnapsack(int capacity, std::vector<int> &weights, std::vector<int> &values, int n) {
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(capacity + 1, -1));
    return FindKnapsackRec(capacity, weights, values, n, dp);
}
// Driver code
int main() {
    std::vector<int> weights = {10, 20, 30, 40};
    std::vector<int> values = {30, 10, 40, 20};
    int capacity = 40;
    int n = 4;
    int result = FindKnapsack(capacity, weights, values, n);
    std::cout << "The maximum value of items in knapsack is: " << result << std::endl;
    return 0;
}

def find_knapsack(capacity, weights, values, n):
    dp = [[-1 for i in range(capacity + 1)] for j in range(n + 1)]
    return find_knapsack_value(capacity, weights, values, n, dp)
def find_knapsack_value(capacity, weights, values, n, dp):
    # Base case
    if n == 0 or capacity == 0:
        return 0
    
    #If we have solved it earlier, then return the result from memory
    if dp[n][capacity] != -1:
        return dp[n][capacity]
 
    #Otherwise, we solve it for the new combination and save the results in the memory
    if weights[n-1] <= capacity:
        dp[n][capacity] = max(
            values[n-1] + find_knapsack_value(capacity-weights[n-1], weights, values, n-1, dp),
            find_knapsack_value(capacity, weights, values, n-1, dp)
            )
        return dp[n][capacity]
    dp[n][capacity] = find_knapsack_value(capacity, weights, values, n-1, dp)
    return dp[n][capacity] 
# Driver code
def main():
    weights = [10, 20, 30, 40]
    values = [30, 10, 40, 20]
    capacity = 40
    n = 4
    
    result = find_knapsack(capacity, weights, values, n)
    print "The maximum value of items in knapsack is: ", result
if __name__ == '__main__':
    main()