Dynamic Programming: Knapsack Problem

April 28, 2023

1335 words/7 min read

Page content

Dynamic Programming is an algorithmic technique to solve constrained, combinatorial optimization problems. The Knapsack here is a metaphor for the constraint. The ‘knapsack’ might as well be a container ship.

Given a set of weights with corresponding values and a knapsack of certain capacity, the problem involves packing the most valuable knapsack with the weights that fit into the knapsack.

What is special about Dynamic Programming problems?

Dynamic programming problems can be broken down into subproblems that have optimal substructure. This means solving a subproblem optimally contributes to the optimal solution of the bigger problem. Additionally, the solutions to the subproblems are themselves overlapping or common to more than one containing problem.

The two approaches

The classical approach to dynamic programming is the bottom-up approach where we solve the major problem by solving each of the subordinate problems with a memory function.

The second approach is the top-down approach which starts with the major problem and recursively solves the subproblems whereby the solution bubbles up.

The first approach, because of the memory function, avoids solving the same subproblems repeatedly. However, it may end up solving some subproblems that do not contribute to the solution. The second approach solves only the necessary subproblems, but might end up solving them repeatedly.

We can indeed have the best of both worlds by combining top-down with memory function.

Recurrence equation and notations

We have weights $w_i$ and corresponding values $v_i$, $i$ varying from $1$ to $n$. $V_{i,j}$ is the value of the knapsack when weights upto $i$ are available and the knapsack capacity is $j$. We are seeking the solution $V_{n,C}$ where $C$ is the capacity of the knapsack.

At the heart of the algorithm are the two recurrence equations:

$$ V_{i,j} = V_{i-1,j},\ if\ j < w_i \tag{1} $$

$$ V_{i,j} = {max(V_{i-1,j}, v_i + V_{i-1, j-w_i})},\ if\ j >= w_i \tag{2} $$

$$ V_{0,j}, V_{i,0} = 0 \ for\ all\ i, j \tag{3} $$

Equation 1 means if the current available weight $w_i$ is greater than the current available capacity $j$ of the knapsack, then continue with the previous state.

Equation 2 means if the current available weight $w_i$ is less than the current available capacity $j$ of the knapsack, then determine whether adding $w_i$ improves the value of the knapsack, over the previous state.

Equation 3 is meant for the initial condition: the first row and first column of solution matrix are 0s.

Implementation notes

We have implemented a class which supports both top-down and bottom-up approaches of the knapsack. Below, are the Python programs that we have implemented:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108


#!/usr/bin/env python3

'''
This is implementation of a 0/1 knapsack class with two methods: classical bottom-
up dynamic programming and top-down with memo.
'''

import numpy as np

class Knapsack():
    '''Class to implement knapsack
       Instantiate with (capacity,weights,values)
       Returns solution matrix, best value, weights picked
    '''
    def __init__(self, capacity = 0, weights = [], values = []):
        # Initialize capacity weights and values, add a leading 0 for ease of
        # computation.
        self._capacity = capacity
        self._weights = [0]+weights
        self._values = [0]+values
        # Initialize solution matrix
        self._V = np.zeros((len(self._weights),self._capacity+1), dtype=int)
        self._V[1:,1:] = -1 # except first row and col, all values -1
        # They get filled via the algorithm
        
    def _pack_bottom_up(self, ):  # deemed private function
        # We traverse the V matrix column-wise for a classical bottom-up dynamic
        # programming approach.

        for j in range(1,self._capacity+1):
            for i in range(1,len(self._weights)):
                # Implement the two recurrence equations here
                if(j-self._weights[i] >= 0):
                    self._V[i,j] = max(self._V[i-1,j], self._values[i]+self._V[i-1,j-self._weights[i]])
                else:
                    self._V[i,j] = self._V[i-1,j]
                  
        return None
        
    def _pack_top_down(self, i , j):    # deemed private function
        # i is index of weight/value j is knapsack capacity
        # go top-down but with memory. Top-down computes only needed sub-problems.
        # memory avoids recomputations.  Best of both worlds.
        if self._V[i,j] < 0:
            if j < self._weights[i]:
                self._V[i,j] = self._pack_top_down(i-1,j)
            else:
                self._V[i,j] = max(self._pack_top_down(i-1,j), self._values[i]+self._pack_top_down(i-1,j-self._weights[i]))                

        return self._V[i,j]
        
    def _get_best_weights(self, ):
        # Get the most valuable weights picked.
        r = len(self._weights)-1
        c = self._capacity
        included_list = []   # Included weight indices

        while(True):
            while self._V[r, c] == self._V[r-1, c]:
                r = r-1
                if r == 0:
                    break
                    
            if r > 0:            
                included_list.append(r)            
                c = c - self._weights[r]
                r = r - 1

            if r == 0 or c <= 0:
                break
                
        return included_list[::-1] # return indices in ascending order.
        
    def pack(self, how = 'bottom_up'):
        # Public interface to pack the knapsack. Default is bottom-up
        # Initialise the solution space for each call
        self._V = np.zeros((len(self._weights),self._capacity+1), dtype=int)
        self._V[1:,1:] = -1 # except first row and col, all values -1
        # They get filled via the algorithm        
        
        # Calling these functions, fills the solution matrix (_V)
        if how == 'bottom_up':
            self._pack_bottom_up()
        else:
            self._pack_top_down(len(self._weights)-1, self._capacity)
            
        # We return the state of the knapsack or the solution
        return self._V, self._V[-1,-1], self._get_best_weights()
        # (solution matrix, best value, weights selected)

                    
if __name__ == "__main__":

    # Instantiate a knapsack
    #my_knapsack = Knapsack(capacity = 5, weights = [2,1,3,2], values = [12,10,20,15])

    my_knapsack = Knapsack(capacity = 10, weights = [2,1,3,2,5,7,8], values = [12,10,20,15,17,28,24])
    print("Capacity:", my_knapsack._capacity, "\nWeights:", my_knapsack._weights[1:], "Values:", my_knapsack._values[1:])
        
    solution_matrix, best_value, best_weights = my_knapsack.pack(how = 'top_down')
    print("Top down solution matrix:\n", solution_matrix)
    print("Best value:", best_value)    
    print("Best weights:", best_weights)    # Print the weight indices, 1 based indexing
    
    solution_matrix, best_value, best_weights = my_knapsack.pack(how = 'bottom_up')
    print("Bottom up solution matrix:\n", solution_matrix)
    print("Best value:", best_value)    
    print("Best weights:", best_weights)

We get the following output:

Capacity: 10 
Weights: [2, 1, 3, 2, 5, 7, 8] Values: [12, 10, 20, 15, 17, 28, 24]
Top down solution matrix:
 [[ 0  0  0  0  0  0  0  0  0  0  0]
 [ 0  0 12 12 12 12 12 12 12 12 12]
 [ 0 10 12 22 -1 22 -1 22 22 -1 22]
 [ 0 10 12 22 -1 32 -1 -1 42 -1 42]
 [ 0 -1 15 25 -1 37 -1 -1 -1 -1 57]
 [ 0 -1 15 25 -1 -1 -1 -1 -1 -1 57]
 [ 0 -1 15 -1 -1 -1 -1 -1 -1 -1 57]
 [ 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 57]]
Best value: 57
Best weights: [1, 2, 3, 4]
Bottom up solution matrix:
 [[ 0  0  0  0  0  0  0  0  0  0  0]
 [ 0  0 12 12 12 12 12 12 12 12 12]
 [ 0 10 12 22 22 22 22 22 22 22 22]
 [ 0 10 12 22 30 32 42 42 42 42 42]
 [ 0 10 15 25 30 37 45 47 57 57 57]
 [ 0 10 15 25 30 37 45 47 57 57 57]
 [ 0 10 15 25 30 37 45 47 57 57 57]
 [ 0 10 15 25 30 37 45 47 57 57 57]]
Best value: 57
Best weights: [1, 2, 3, 4]

We observe that the bottom-up approach has solved all the sub-problems whereas the top-down approach has solved only the necessary sub-problems.

To get the latest version of the code, refer to this github link.