Knapsack Problem in Python
This article was published as a part of the Data Science Blogathon.
Introduction
This article will focus on several approaches for solving the Knapsack challenge in Python. The greedy methodology, dynamic programming, or a brute force approach can all be used to solve the knapsack problem. Both the problem and solution are analyzed using the knapsack problem.
Given the weights and values of n objects, we must find weight sets that can fill a bag to its maximum value w. This set should not include more than the given number of elements. The expected outcome is an integer holding a count of up to a given number of elements.
What is Python’s Knapsack Problem?
A knapsack problem algorithm is a strategy for tackling combinatorial optimization constructively. The problem is just a particular stack of objects, each having a specific weight and value. As a consequence, the programmer must select the number of elements to include in a stack in such a way that the total weight of the stack is less than or equal to a given limit. Furthermore, the entire value is maximized. It gets its name from the fixed-size bag that must be stuffed full of the most valuable objects.
Problem Approach
- A knapsack problem is a constructive strategy using a predefined set of objects and their weights and values.
- So, the first step for the programmer is to give a number to each element so that it is included in the stack, and then to verify if it follows that the overall weight is less than or equal to a predetermined limit.
- In addition, the programmer must ensure that the given set has the maximum number of elements.
Constraints for the Knapsack Problem in Python
Understanding the constraints is one of the most important aspects of learning competitive programming. These constraints will assist you in determining which algorithm to adopt to combat the problem.
- 3 ≤ N ≤ 100000;
- 1 ≤ W ≤ 2, fоr eасh item;
- 1 ≤ С ≤ 109, fоr eасh item.
- Time Limit: 1 Sec.
- Source File Limit: 50000 Bytes
Here,
N = Number of items
W = The weight of the item
C = The Cost of the item
Note: Please keep in mind that these constraints may vary depending on your problem statement.
Various methods for solving the Knapsack problem in Python
The three methods listed below are the only ones available 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
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)
Output:
Расk 0 - Weight 10 - Vаlue 25 Расk 0 - Weight 10 - Vаlue 25 Расk 0 - Weight 10 - Vаlue 25 Расk 2 - Weight 4 - Vаlue 6 Расk 3 - Weight 2 - Vаlue 2 Mаx Vаlue: 83
Explanation:
Greedy algorithms are used to solve optimization issues, i.e., to find the optimum solution given a set of criteria. Greedy algorithms make optimum local preferences in the belief that they will result in the best solution. However, the greedy approach’s answer is never optimal. Greedy approaches are effective for solving the fractional knapsack problem. However, the output for the 0/1 knapsack problems is not necessarily optimum.
The above statement concludes that the greedy approach’s concept is to compute the (value/weight) ratio. Sort the ratios in descending order. Select the first ratio, which is the maximum package. The knapsack’s size can hold that package (remain > weight). Each time a package is placed in the knapsack, the size of the knapsack is reduced.
Note: The 0/1 knapsack problem is a subset of the knapsack problem in that the knapsack is not filled with fractional elements.
Dynamic Programming
Example:
def knapSack(W, wt, val, n):
K = [[0 fоr x in rаnge(W + 1)] fоr x in rаnge(n + 1)]
# Build tаble K[][] in bоttоm uр mаnner
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:
220
Explanation:
The Dynamic Programming technique differentiates the problem into subproblems. Subproblems are further subdivided into smaller subproblems. Until you have subproblems that are readily solved. The concept behind Knapsack dynamic programming is to store the answers to solved subproblems in a table.
All potential weights from ‘1’ to ‘W’ are the columns in the table, and weights are the rows.
In the above example, the state DP[i][j] reflects the greatest value of ‘j-weight’ considering all values from ‘1 to ith’. So, if we consider ‘wi’ (weight in ‘ith’ row), it is added to all columns with ‘weight values > wi’.
There are two options: fill or leave ‘wi’ blank in that particular column. If we do not enter the ‘ith’ weight in the ‘jth’ column, the DP[i][j] will be same as DP[i-1][j]. However, if we fill the weight, DP[i][j] equals the value of ‘wi’+ the value of the column weighing ‘j-wi’ on the former row. As a result, we choose the best of these two options to fill the present condition.
Python’s Knapsack Problem: A Brute Force Approach
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:
220
Explanation:
Using brute force to solve the Knapsack problem is a simple solution. There will be 2n potential combinations of elements for the knapsack if there are n elements to pick from. An element is either selected or not. A bit string of 0’s and 1’s with a length equal to the number of elements, n, is created. If the ith symbol in a bit string is 0, the element is not selected. And if the answer is 1, the element is picked.
Conclusion
Some of the key highlights of the article are as follow:
- A knapsack problem technique improves combinatorial optimization.
- Please keep in mind that constraints in different problems may change based on how you describe your problem.
- The knapsack problem technique can be implemented in multiple ways.
- Python’s knapsack problem can be solved more efficiently using Dynamic Programming than either of the other two approaches.
- Dynamic Programming has a lower time and space complexity than other approaches and is more effective.
Frequently Asked Questions
Que- What is the use of the knapsack problem?
The knapsack problem is an optimization problem that illustrates both the problem and its solution. It gets its name from the fact that the amount of goods that can fit inside a fixed-size backpack is limited.
Que- What is the multiple knapsack problem?
The multiple knapsack problem is a generalization of the standardized knapsack problem (KP) from a single knapsack to m knapsacks with (possibly) different capacities.
Que- Why is the knapsack problem NP-complete?
The knapsack problem in python is NP-complete because the subset-sum of every known NP-complete is polynomially reducible to the knapsack problem, and so every problem is reducible to the knapsack problem.
The media shown in this article is not owned by Analytics Vidhya and is used at the Author’s discretion.
Currently, I Am pursuing my Bachelors of Technology( B.Tech) from Vellore Institute of Technology. I am very enthusiastic about programming and its real applications including software development, machine learning and data science.
