Knapsack problem
Lesson 7 of 15 in Coddy's Dynamic Programming 101 course.
The Knapsack problem is a classic optimization problem in computer science. The problem statement is simple: given a set of items, each with a weight and a value, determine the items to include in a collection so that the total weight is less than or equal to a given limit and the total value is maximized.
There are two types of the knapsack problem:
- 0/1 Knapsack: In this version, the thief cannot take fractions of the item, either they take it completely or leave it.
- Fractional Knapsack: In this version, the thief can take fractions of the item, i.e., a portion of an item can be taken.
Challenge
MediumWrite a function named knapsack that solves the 0/1 knapsack problem. The function should take three inputs:
- A list of weights of n items (w1, w2, ... , wn).
- A list of values of n items (v1, v2, ... , vn).
- The maximum weight capacity of the knapsack (W).
The function should then output the maximum value that can be achieved by filling the knapsack.
For example:
weights = [10, 20, 30]
values = [60, 100, 120]
W = 50
knapsack(weights, values, W)Output:
220 # taking the 2 largest itemsTry it yourself
def knapsack(wrights, values, W):
# Write code hereAll lessons in Dynamic Programming 101
3Dynamic programming algorithms
Longest common subsequenceKnapsack problemCoin change problemEdit distance