0/1 Knapsack
Understand how to solve the 0 1 Knapsack problem by selecting items to maximize total value without exceeding capacity. Explore dynamic programming techniques to implement efficient solutions using memoization and tabulation.
We'll cover the following...
Statement
You are given items whose weights and values are known, as well as a knapsack to carry these items. The knapsack cannot carry more than a certain maximum weight, known as its capacity.
You need to maximize the total value of the items in your knapsack, while ensuring that the sum of the weights of the selected items does not exceed the capacity of the knapsack.
If there is no combination of weights whose sum is within the capacity constraint, return .
Notes:
- An item may not be broken up to fit into the knapsack, i.e., an item either goes into the knapsack in its entirety or not at all.
- We may not add an item more than once to the knapsack.
Constraints:
-
capacity -
values.length weights.lengthvalues.length-
values[i] -
weights[i]capacity
Examples
Understand the problem
Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:
0/1 Knapsack
You have three items with weights , , and , respectively. You have a knapsack with a capacity of . How many different combinations of items can you include in the knapsack?
3
4
5
6
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Try it yourself
Implement your solution in the following coding playground:
import java.util.*;class FindMaxKnapsackProfit {public static int findMaxKnapsackProfit(int capacity, int [] weights, int [] values) {// Replace this placeholder return statement with your codereturn 0;}}