Python Program to Solve 0-1 Knapsack Problem using Dynamic Programming with Bottom-Up Approach

This is a Python program to solve the 0-1 knapsack problem using dynamic programming with bottom-up approach.

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. First m[0][w] is initialized to 0 for all 0 <= w <= capacity. 6. For item i, if weight[i] > w, then m[i][w] = m[i – 1][w].
7. If weight[i] <= w, then m[i][w] = (m[i - 1][w - weight[i]] + value[i]) or m[i][w] = m[i - 1][w], whichever is larger. 8. The table is filled from top to bottom row. 9. m[n][capacity] is returned.

Here is the source code of a Python program to solve the 0-1 knapsack problem using dynamic programming with bottom-up approach. 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)]
 
    for w in range(capacity + 1):
        m[0][w] = 0
 
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weight[i] > w:
                m[i][w] = m[i - 1][w]
            else:
                m[i][w] = max(m[i - 1][w - weight[i]] + value[i], 
                              m[i - 1][w])
 
    return m[n][capacity]
 
 
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 maximum 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.