Python Program to Solve 0-1 Knapsack Problem using Dynamic Programming with Memoization

This is a Python program to solve the 0-1 knapsack problem using dynamic programming with top-down approach or memoization.

In the 0-1 knapsack problem, we are given a set of n items. For each item i, it has a value v(i) and a weight w(i) where 1 <= i <= n. We are given a maximum weight W. The problem is to find a collection of items such that the total weight does not exceed W and the total value is maximized. A collection of items means a subset of the set of all items. Thus, an item can either be included just once or not included.

1. The function knapsack is defined.
2. It takes three arguments: two lists value and weight; and a number capacity.
3. It returns the maximum value of items that doesn’t exceed capacity in weight.
4. The function creates a table m where m[i][w] will store the maximum value that can be attained with a maximum capacity of w and using only the first i items.
5. It calls knapsack_helper on m with i=n and w=capacity and returns its return value.
6. The function knapsack_helper takes 5 arguments: two lists value and weight; two numbers i and w; and a table m.
7. It returns the maximum value that can be attained using only the first i items while keeping their total weight not more than w.
8. If m[i][w] was already computed before, this value is immediately returned.
9. If i = 0, then 0 is returned.
10. If weight[i] > w, then m[i][w] is set to m[i – 1][w].
11. Otherwise, m[i][w] = (m[i – 1][w – weight[i]] + value[i]) or m[i][w] = m[i – 1][w], whichever is larger.
12. The above computations are done by recursively calling knapsack_helper.

Here is the source code of a Python program to solve the 0-1 knapsack problem using dynamic programming with top-down approach or memoization. The program output is shown below.

def knapsack(value, weight, capacity):
    """Return the maximum value of items that doesn't exceed capacity.
 
    value[i] is the value of item i and weight[i] is the weight of item i
    for 1 <= i <= n where n is the number of items.
 
    capacity is the maximum weight.
    """
    n = len(value) - 1
 
    # m[i][w] will store the maximum value that can be attained with a maximum
    # capacity of w and using only the first i items
    m = [[-1]*(capacity + 1) for _ in range(n + 1)]
 
    return knapsack_helper(value, weight, m, n, capacity)
 
 
def knapsack_helper(value, weight, m, i, w):
    """Return maximum value of first i items attainable with weight <= w.
 
    m[i][w] will store the maximum value that can be attained with a maximum
    capacity of w and using only the first i items
    This function fills m as smaller subproblems needed to compute m[i][w] are
    solved.
 
    value[i] is the value of item i and weight[i] is the weight of item i
    for 1 <= i <= n where n is the number of items.
    """
    if m[i][w] >= 0:
        return m[i][w]
 
    if i == 0:
        q = 0
    elif weight[i] <= w:
        q = max(knapsack_helper(value, weight,
                                m, i - 1 , w - weight[i])
                + value[i],
                knapsack_helper(value, weight,
                                m, i - 1 , w))
    else:
        q = knapsack_helper(value, weight,
                            m, i - 1 , w)
    m[i][w] = q
    return q
 
 
n = int(input('Enter number of items: '))
value = input('Enter the values of the {} item(s) in order: '
              .format(n)).split()
value = [int(v) for v in value]
value.insert(0, None) # so that the value of the ith item is at value[i]
weight = input('Enter the positive weights of the {} item(s) in order: '
               .format(n)).split()
weight = [int(w) for w in weight]
weight.insert(0, None) # so that the weight of the ith item is at weight[i]
capacity = int(input('Enter maximum weight: '))
 
ans = knapsack(value, weight, capacity)
print('The maximum value of items that can be carried:', ans)

1. The user is prompted to enter the number of items n.
2. The user is then asked to enter n values and n weights.
3. A None value is added at the beginning of the lists so that value[i] and weight[i] correspond to the ith item where the items are numbered 1, 2, …, n.
4. The function knapsack is called to get the maxmimum value.
5. The result is then displayed.

Case 1:
Enter number of items: 3
Enter the values of the 3 item(s) in order: 60 100 120
Enter the positive weights of the 3 item(s) in order: 10 20 30
Enter maximum weight: 50
The maximum value of items that can be carried: 220
 
Case 2:
Enter number of items: 5
Enter the values of the 5 item(s) in order: 10 5 20 40 30
Enter the positive weights of the 5 item(s) in order: 4 1 10 20 7
Enter maximum weight: 10
The maximum value of items that can be carried: 35
 
Case 3:
Enter number of items: 1
Enter the values of the 1 item(s) in order: 5
Enter the positive weights of the 1 item(s) in order: 5
Enter maximum weight: 2
The maximum value of items that can be carried: 0

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

If you find any mistake above, kindly email to [email protected]