# Heard that the Knapsack Problem is Difficult? This Summary is Here to Save You
Before the end of the year, we covered all the aspects of the knapsack problem. Now it's time to summarize the knapsack problem comprehensively.
The knapsack problem is a very important part of dynamic programming, so I will separate it for a detailed summary. Once we've finished the dynamic programming section, we'll do an overall review of dynamic programming.
The relationship between these common knapsack problems is depicted as follows:
This diagram clearly distinguishes the relationships among these common knapsack problems.
When explaining the knapsack problem, we followed these five steps to gradually analyze it. As many of you may have experienced, understanding these five steps thoroughly can lead to a deeper understanding of dynamic programming.
- Determine the dp array (dp table) and the meaning of its indices
- Determine the state transition formula
- How to initialize the dp array
- Determine the iteration order
- Derive the dp array with examples
Each of these five steps is critical, but determining the state transition formula and iteration order have regularity and representativeness, so I will summarize the knapsack problem mainly from these two points below.
# Knapsack State Transition Formula
Question: Can the knapsack be fully packed (or what is the maximum that can be packed)? Formula: dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);. Related problems:
- Dynamic Programming: 0416.Partition Equal Subset Sum (opens new window)
- Dynamic Programming: 1049.Last Stone Weight II (opens new window)
Question: How many ways to fill the knapsack? Formula: dp[j] += dp[j - nums[i]]. Related problems:
- Dynamic Programming: 0494.Target Sum (opens new window)
- Dynamic Programming: 0518.Coin Change II (opens new window)
- Dynamic Programming: 0377.Combination Sum IV (opens new window)
- Dynamic Programming: 0070.Climbing Stairs Complete Knapsack Version (opens new window)
Question: What is the maximum value that can fill the knapsack? Formula: dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);. Related problems:
Question: What is the minimum number of items needed to fill the knapsack? Formula: dp[j] = min(dp[j - coins[i]] + 1, dp[j]);. Related problems:
- Dynamic Programming: 0322.Coin Change (opens new window)
- Dynamic Programming: 0279.Perfect Squares (opens new window)
# Iteration Order
# 01 Knapsack
In Knapsack Theory 01 Knapsack-1 (opens new window), we discussed that in a two-dimensional dp array implementation of the 01 knapsack, either iterating over items first or iterating over the knapsack capacity first works, and the second loop is from small to large.
And in Knapsack Theory 01 Knapsack-2 (opens new window), we discussed that for a one-dimensional dp array implementation of the 01 knapsack, the items must be iterated over first, followed by the knapsack capacity, and the second loop is from large to small.
The iteration order in a one-dimensional dp array differs significantly from the two-dimensional dp array implementation of the 01 knapsack, so take note!
# Complete Knapsack
After discussing the 01 knapsack, let's look at the complete knapsack.
In Knapsack Problem Theory Basics Complete Knapsack (opens new window), we explained a pure one-dimensional dp array implementation of the complete knapsack, where both iterating over items first and iterating over the knapsack first works, and the second loop is from small to large.
However, this is only true for a pure complete knapsack. If the problem varies slightly, the order of the two for loops will change.
To calculate combinations, the outer for loop iterates over items, and the inner for loop iterates over the knapsack.
To calculate permutations, the outer for loop iterates over the knapsack, and the inner for loop iterates over items.
Relevant problems:
- To calculate combinations: Dynamic Programming: 0518.Coin Change II (opens new window)
- To calculate permutations: Dynamic Programming: 0377.Combination Sum IV (opens new window), Dynamic Programming: 0070.Climbing Stairs Complete Knapsack Version (opens new window)
If calculating the minimum number, the order of the two for loops does not matter. Relevant problems:
- To calculate the minimum number: Dynamic Programming: 0322.Coin Change (opens new window), Dynamic Programming: 0279.Perfect Squares (opens new window)
For the knapsack problem, the state transition formula is relatively easy, but the iteration order is the challenging part. Understanding the iteration order thoroughly indicates a true grasp of the problem.
# Summary
This summary of the knapsack problem provides a high-level overview, focusing on the most critical two steps: the state transition formula and iteration order, abstracting from all related LeetCode problems.
In addition, each point is paired with corresponding LeetCode problems.
Lastly, if you want to learn about the multiple knapsack problem, see Knapsack Problem Theory Basics - Multiple Knapsack (opens new window). Currently, there are no LeetCode problems on multiple knapsack, nor is it a major focus during interviews.
Mastering the content I’ve summarized here will provide you with a deep understanding of the knapsack problem, which will be more than sufficient for tackling knapsack problems in interviews!
Knapsack problem summary:
This diagram was excellently drawn and shared by a member named 海螺人 (opens new window) from the Keetcoder Knowledge Circle (opens new window).