Heard that the Knapsack Problem is Difficult? This Summary is Here to Save You

July 28, 2025 · View on GitHub

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:

416.Knapsack Theory 01 Knapsack-11

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.

  1. Determine the dp array (dp table) and the meaning of its indices
  2. Determine the state transition formula
  3. How to initialize the dp array
  4. Determine the iteration order
  5. 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:

Question: How many ways to fill the knapsack? Formula: dp[j] += dp[j - nums[i]]. Related problems:

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:

Iteration Order

01 Knapsack

In Knapsack Theory 01 Knapsack-1, 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, 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, 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:

If calculating the minimum number, the order of the two for loops does not matter. Relevant problems:

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. 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 海螺人 from the Keetcoder Knowledge Circle.