0 and 1 Knapsack
MetaThe problem
Given two integer arrays, val and wt, each of size N, which represent the values and weights of N items respectively, and an integer W representing the maximum capacity of a knapsack, determine the maximum value achievable by selecting a subset of the items such that the total weight of the selected items does not exceed the knapsack capacity W.
Each item can either be picked in its entirety or not picked at all (0-1 property). The goal is to maximize the sum of the values of the selected items while keeping the total weight within the knapsack's capacity.
Input: val = [60, 100, 120], wt = [10, 20, 30], W = 50 Output: 220 Explanation: Select items with weights 20 and 30 for a total value of 100 + 120 = 220.
Input: val = [10, 40, 30, 50], wt = [5, 4, 6, 3], W = 10 Output: 90 Explanation: Select items with weights 4 and 3 for a total value of 40 + 50 = 90.
**Input: **val = [20, 5, 10, 40, 15, 25], wt = [1, 2, 3, 8, 7, 4], W = 10
- 1 ≤ N ≤ 500
- 1 ≤ W ≤ 1000
- 1 ≤ wt[i] ≤ 500
- 1 ≤ val[i] ≤ 500
cpp
class Solution{
public:
int knapsack01(vector<int>& wt, vector<int>& val, int n, int W) {
//your code goes here
}
};java
class Solution {
public int knapsack01(int[] wt, int[] val, int n, int W) {
}
}python
class Solution:
def knapsack01(self, wt, val, n, W):javascript
class Solution {
knapsack01(wt, val, n, W) {
}
}csharp
class Solution
{
public int knapsack01(int[] wt, int[] val, int n, int W)
{
}
}go
func knapsack01(wt, val []int, n, W int) int {
}Stuck? Show a way to structure it+
- 01Let dp[w] be the best value achievable with capacity w.
- 02Process each item once.
- 03For each item, update capacities from W down to its weight.
- 04Take max of keeping dp[w] or using the item plus dp[w-weight].
Reference answer
Then expect these follow-ups
How does unbounded knapsack change the loop order?
Tests: DP invariants
How would you reconstruct the chosen item set?
Tests: solution reconstruction
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question