Introduction to Knapsack Problem Python
The following article provides an outline for Knapsack Problem Python. The knapsack problem is used to analyze both problem and solution. In this problem, we will be given n items along with the weights and values of it. The task is to choose the set of weights that fill the maximum capacity of the bag. The condition here is the set which we are choosing must contain the highest number of elements than the other sets and the total weight must be less than or equal to the given weight. That means weight must be lesser and at the same time value must be as large as possible. The main arises in the Knapsack is when the programmers should choose from non-divisible elements. The output will be an integer with the number of items we have chosen in the bag.
- A knapsack problem is a constructive approach that is basically about a given set of items along with their weights and values.
- So, the first step of the programmer is to set each item’s number so that it includes in the collection and finally to check whether the total weight is less than or equal to a specific limit.
- The programmer also needs to ensure that the particular set is containing the maximum number of elements.
Constraints for Knapsack Problem
Understanding constraints is the most important part of any problem. This constraint helps you understand which algorithm to use to solve the problem. Constraints for the Knapsack problem are:
- 100000 ≥ N ≥ 3
- 2 ≥ W ≥ 1, for each given item
- 109 ≥ C ≥ 1, for each given item
- Time Limit: 1 Second.
- Source File Limit: 50000 Bytes
- N denotes the number of items.
- W denotes the weight of the item.
- C denotes the cost of the item.
Solving the Knapsack Problem
There are three ways to solve a knapsack problem using python programming.
- Greedy Method
- Dynamic Programming
- Brute Force
1. Greedy Method
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 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) class FractionalKnapsack(object): def __init__(self): 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)
- The Greedy algorithm’s idea is to calculate the ratio of value and weight then choose the ratios by sorting them in descending order. The first ratio is the maximum package number, so choose the first ratio.
- You need to fill the knapsack until remain is greater than the weight when it crosses the weight the loop should break and display the output value.
2. Dynamic Programming
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 to 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))
- In Dynamic Programming, the given problem is divided into subproblems.
- The subproblems are again divided into many subproblems. They get divided until you get subproblems that can be easily solved.
3. Brute Force
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))
- Brute Force solves the problem by checking if there are ‘n’ items from which you have to choose, then there is a possibility to get 2n combinations of elements in the Knapsack. Whether the item is either chosen or not, a bit-string of 0’s and 1’s is obtained, whose length will be equal to the number of items.
- If the ‘i’th symbol of that string is 0, then consider that the item is not chosen. And if the ‘i’th symbol of that string is 1, consider the item as chosen.
In this article, we have discussed the approaches to solve a Knapsack problem. n items are given along with the weights and values of it. The task is to choose the set of weights that fill the maximum capacity of the bag by fulfilling all the given conditions. The first step of the programmer is to set each item’s number so that it includes in the collection and finally to check whether the total weight is less than or equal to a specific limit. The Greedy algorithm’s idea is to calculate the ratio of value and weight then choose the ratios by sorting them in descending order. In Dynamic Programming, the given problem is divided into subproblems. Brute force is the best approach to solve any Knapsack problem. If there are ‘n’ items from which you have to choose, then there is a possibility to get 2n combinations of elements in the Knapsack. By using the combinations the problem is solved.
This is a guide to Knapsack Problem Python. Here we discuss the introduction, problem approach, constraints, and solving the Knapsack problem. You may also have a look at the following articles to learn more –