Knapsack Problem in Python With 3 Unique Ways to Solve

Hello Programmers, in this article, we will discuss ways to solve the Knapsack problem in python using different approaches. The different approaches to solving the knapsack problem are – greedy method, dynamic programming, and brute force approach. Before we start with examples of the knapsack problem, let me briefly brief you about the knapsack problem.

For given weights and values of n items, we have to choose sets of weights that can fill up the maximum capacity w in a bag of capacity W. This set should contain a maximum number of items. The expected output is an integer with a count of a maximum number of items.

Contents

What is Knapsack Problem in Python?

A knapsack problem algorithm is a constructive approach to combinatorial optimization. The problem is basically about a given set of items, each with a specific weight and a value. Therefore the programmer needs to determine each item’s number to include in a collection so that the total weight is less than or equal to a given limit. And also, the total value is maximum. It derives its name from the fixed-size knapsack that must be filled up to its limit with the most valuable items.

Practical Application of Knapsack Problem Python

The practical application of The knapsack problem algorithm is used in resource allocation. However, the decision-makers have to choose from a set of projects or tasks under a fixed budget or time constraint.

Note: 0/1 knapsack problem is a special case knapsack problem that does not fill the knapsack with fractional items.

Constraints For Knapsack Problem in Python

In competitive programming, understanding the constraints is a valuable part. These constraints can help you identify which algorithm you need to use to solve this problem.

3 ≤ N ≤ 100000;
1 ≤ W ≤ 2, for each item;
1 ≤ C ≤ 10⁹, for each item.
Time Limit: 1 Sec.
Source File Limit: 50000 Bytes

Where N stands for a number of items, W stands for the weight of the item and C stands for Cost of the item.

Note: Please remember that these constraints might change according to your problem statement. The above constraints refer to the Knapsack problem from the CodeChef platform.

Different approaches to solve Knapsack Problem Python

Following 3 ways are the only available ways to solve the Knapsack Problem in Python –

Greedy Method
Dynamic programming
Brute Force

Greedy Method

EXAMPLE:

class KnapsackPackage(object): 
    """ Knapsack Package Data Class """
    def __init__(self, weight, value): 
        self.weight = weight 
        self.value = value 
        self.cost = value / weight 

    def __lt__(self, other): 
        return self.cost < other.cost

class FractionalKnapsack(object):
    def __init__(self):
        pass

    def knapsackGreProc(self, W, V, M, n):
        packs = []
        for i in range(n): 
            packs.append(KnapsackPackage(W[i], V[i]))
        packs.sort(reverse = True)
        remain = M
        result = 0
        i = 0
        stopProc = False
        while (stopProc != True):
            if (packs[i].weight <= remain):
                remain -= packs[i].weight;
                result += packs[i].value;
            print("Pack ", i, " - Weight ", packs[i].weight, " - Value ", packs[i].value)
            if (packs[i].weight > remain):
                i += 1
            if (i == n):
                stopProc = True            
        print("Max Value:\t", result)

if __name__ == "__main__": 
    W = [15, 10, 2, 4] 
    V = [30, 25, 2, 6] 
    M = 37
    n = 4
    proc = FractionalKnapsack()
    proc.knapsackGreProc(W, V, M, n)

OUTPUT:

Pack  0  - Weight  10  - Value  25
Pack  0  - Weight  10  - Value  25
Pack  0  - Weight  10  - Value  25
Pack  2  - Weight  4  - Value  6
Pack  3  - Weight  2  - Value  2
Max Value:	 83

Explanation:

Greedy algorithms are used to solve optimization problems, i.e., find the best solution based upon given criteria. Greedy algorithms implement optimal local selections in the hope that those selections will lead to the best solution. However, the solution to the greedy method is always not optimal. Greedy methods work well for the fractional knapsack problem. However, for the 0/1 knapsack problem, the output is not always optimal.

In conclusion, The greedy method’s idea is to calculate the (value/weight) ratio. Sort the ratios in descending order. Choose the first ratio, which is the maximum package. The capacity of the knapsack can contain that package (remain > weight). Every time a package is put into the knapsack, it will also reduce the knapsack’s capacity.

Dynamic Programming

EXAMPLE:

def knapSack(W, wt, val, n): 
    K = [[0 for x in range(W + 1)] for x in range(n + 1)] 
  
    # Build table K[][] in bottom up manner 
    for i in range(n + 1): 
        for w in range(W + 1): 
            if i == 0 or w == 0: 
                K[i][w] = 0
            elif wt[i-1] <= w: 
                K[i][w] = max(val[i-1] 
                          + K[i-1][w-wt[i-1]],   
                              K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 
  
    return K[n][W] 
  
  
# Driver code 
val = [60, 100, 120] 
wt = [10, 20, 30] 
W = 50
n = len(val) 
print(knapSack(W, wt, val, n))

OUTPUT:

Explanation:

Dynamic Programming approach divides the problem to be solved into subproblems. The subproblems are further kept on dividing into smaller subproblems. Until you get subproblems that can be solved easily. The idea of Knapsack dynamic programming is to use a table to store the solutions of solved subproblems.

In the table, all the possible weights from ‘1’ to ‘W’ serve as the columns and weights are kept as the rows.
The state DP[i][j] in the above example denotes the maximum value of ‘j-weight’ considering all values from ‘1 to ith’. So if we consider ‘wi’ (weight in ‘ith’ row) it is put in all columns which have ‘weight values > wi’. Two possibilities occur – to fill or not to fill ‘wi’ in the given column. If we do not fill ‘ith’ weight in ‘jth’ column then DP[i][j] state will be same as DP[i-1][j].But if we fill the weight, DP[i][j] will be equal to the value of ‘wi’+ value of the column weighing ‘j-wi’ in the previous row. We therefore take the maximum of these two possibilities to fill the current state.

Brute Force Approach For Knapsack Problem Python

EXAMPLE:

def knapSack(W, wt, val, n):
   # initial conditions
   if n == 0 or W == 0 :
      return 0
   # If weight is higher than capacity then it is not included
   if (wt[n-1] > W):
      return knapSack(W, wt, val, n-1)
   # return either nth item being included or not
   else:
      return max(val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
         knapSack(W, wt, val, n-1))
# To test above function
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print (knapSack(W, wt, val, n))

OUTPUT:

EXPLANATION:

Brute force is a very straightforward approach to solving the Knapsack problem. For n items to
choose from, then there will be 2n possible combinations of items for the knapsack. An item is either chosen or not. A bit string of 0’s and 1’s is generated, which is a length equal to the number of items, i.e., n. If the ith symbol of a bit string is 0, then that item is not chosen. And if it is 1, the item is chosen.

Must Read

Conclusion

In this article, we discussed various approaches to implement the knapsack problem algorithm. Above all three ways, the Dynamic Programing approach is the best method to solve Python’s knapsack problem. In conclusion, we can say it is very straightforward and simple to understand code. The time and space complexity of Dynamic Programming is also more efficient than the others.

Still have any doubts or questions, do let me know in the comment section below. I will try to help you as soon as possible.

Happy Pythoning!