1. Knapsack Problem Overview
The knapsack problem is a combinatorial optimization problem in the NP - complete class. It can be described as: Given a set of items, each with a weight and a value, under a limited total weight, how to select items to maximize the total value.
Based on the number of each item, it is classified as follows:
- 01 Knapsack: Each item is unique (only one available).
- Unbounded Knapsack: Each item is available in unlimited quantities.
- Multiple Knapsack: Each item has at most
sicopies. - Mixed Knapsack: Items may have any of the above three availability scenarios.
- Group Knapsack: Items are divided into
ngroups, with several items in each group, and at most one item can be selected from each group.
Further, based on whether the knapsack must be filled:
- The knapsack may or may not be filled.
- The knapsack must be filled.
Optimization methods:
- Space optimization using rolling arrays.
- Monotonic queue optimization.
- Greedy optimization.
Based on the number of constraints:
- Single constraint (e.g., volume - typical knapsack problem).
- Two constraints (e.g., volume + weight - two - dimensional cost knapsack problem).
Based on different problem requirements:
- Output the solution.
- Calculate the number of solutions.
- Find the optimal solution.
- Check solution feasibility.
There are many other classifications, but a basic understanding is sufficient. The knapsack problem has a wide variety of types and problems, with varying difficulty. However, all types evolve from the 01 knapsack problem, so mastering the 01 knapsack is crucial.
2. Related Programming Problems
2.1 01 Knapsack Problem
2.1.1 01 Knapsack (Template)
Problem Link [Template] 01 Knapsack - Nowcoder (nowcoder.com)
Algorithm Principle The 01 knapsack problem deals with selecting items (each with one copy) to maximize value under a weight limit. The core is the state transition: for each item, decide to include or exclude it, updating the maximum value for each possible weight capacity.
Code
#include <iostream>
#include <cstring>
using namespace std;
#define MAX_SIZE 1010
int itemCount, capacity;
int weights[MAX_SIZE], values[MAX_SIZE];
int dpTable[MAX_SIZE][MAX_SIZE];
int main() {
// Read input
cin >> itemCount >> capacity;
for (int i = 1; i <= itemCount; ++i) {
cin >> weights[i] >> values[i];
}
// Solve the first sub - problem (max value, not necessarily full)
for (int i = 1; i <= itemCount; ++i) {
for (int j = 1; j <= capacity; ++j) {
dpTable[i][j] = dpTable[i - 1][j]; // Do not select the i - th item
if (j >= weights[i]) { // Ensure there is enough space for the i - th item
dpTable[i][j] = max(dpTable[i][j], values[i] + dpTable[i - 1][j - weights[i]]); // Select the i - th item
}
}
}
cout << dpTable[itemCount][capacity] << endl;
// Solve the second sub - problem (max value, must be full)
memset(dpTable, 0, sizeof(dpTable));
for (int j = 1; j <= capacity; ++j) {
dpTable[0][j] = -1; // -1 indicates that filling the knapsack to volume j exactly is not feasible
}
for (int i = 1; i <= itemCount; ++i) {
for (int j = 1; j <= capacity; ++j) {
dpTable[i][j] = dpTable[i - 1][j]; // Do not select the i - th item
if (j >= weights[i] && dpTable[i - 1][j - weights[i]] != -1) { // Condition 1: enough space; Condition 2: can fill exactly
dpTable[i][j] = max(dpTable[i][j], values[i] + dpTable[i - 1][j - weights[i]]); // Select the i - th item
}
}
}
cout << (dpTable[itemCount][capacity] == -1 ? 0 : dpTable[itemCount][capacity]) << endl;
}
// Space optimization (rolling array)
int optimizedDp[MAX_SIZE];
int main() {
// Read input...
// Solve the first sub - problem
for (int i = 1; i <= itemCount; ++i) {
for (int j = capacity; j >= weights[i]; --j) { // Traverse from right to left to avoid overwriting
optimizedDp[j] = max(optimizedDp[j], values[i] + optimizedDp[j - weights[i]]);
}
}
cout << optimizedDp[capacity] << endl;
// Solve the second sub - problem
memset(optimizedDp, 0, sizeof(optimizedDp));
for (int j = 1; j <= capacity; ++j) {
optimizedDp[j] = -1; // -1 indicates that filling the knapsack to volume j exactly is not feasible
}
for (int i = 1; i <= itemCount; ++i) {
for (int j = capacity; j >= weights[i]; --j) {
if (optimizedDp[j - weights[i]] != -1) {
optimizedDp[j] = max(optimizedDp[j], values[i] + optimizedDp[j - weights[i]]);
}
}
}
cout << (optimizedDp[capacity] == -1 ? 0 : optimizedDp[capacity]) << endl;
}
2.1.2 Partition Equal Subset Sum
Problem Link 416. Partition Equal Subset Sum - LeetCode
Algorithm Principle This problem is a variant of the 01 knapsack where we need to split the array into two subsets with equal sum. It requires the knapsack (subset) to be exactly filled with half the total sum of the array.
Code
class Solution {
public:
bool canPartition(vector<int>& nums) {
int size = nums.size();
int totalSum = 0;
for (auto num : nums) {
totalSum += num;
}
if (totalSum % 2 == 1) { // Odd sum can't be split into two equal integers
return false;
}
vector<bool> dp(totalSum / 2 + 1);
dp[0] = true; // Base case: sum 0 is achievable with empty subset
for (int i = 1; i <= size; ++i) {
for (int j = totalSum / 2; j >= nums[i - 1]; --j) {
dp[j] = dp[j] || dp[j - nums[i - 1]]; // Update if current or remaining sum is achievable
}
}
return dp[totalSum / 2];
}
};
2.1.3 Target Sum
Problem Link 494. Target Sum - LeetCode
Algorithm Principle We need to assign '+' or '-' to each number to get a target sum. It can be transformed into a 01 knapsack problem where we find a subset with a specific sum (derived from the target and total sum of the array).
Code
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int size = nums.size();
int totalSum = 0;
for (auto num : nums) {
totalSum += num;
}
int positiveSum = (totalSum + target) / 2;
if (positiveSum < 0 || (totalSum + target) % 2 == 1) { // Invalid sum or odd total
return 0;
}
vector<int> dp(positiveSum + 1);
dp[0] = 1; // One way to get sum 0 (empty subset)
for (int i = 1; i <= size; ++i) {
for (int j = positiveSum; j >= nums[i - 1]; --j) {
dp[j] += dp[j - nums[i - 1]]; // Accumulate the number of ways
}
}
return dp[positiveSum];
}
};
2.1.4 Last Stone Weight II
Problem Link 1049. Last Stone Weight II - LeetCode
Algorithm Principle The goal is to minimize the final stone weight by splitting stones into two subsets with as close sums as possible. It's a 01 knapsack problem where we aim to maximize the sum of one subset (up to half the total sum of stones).
Code
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int size = stones.size();
int totalSum = 0;
for (auto stone : stones) {
totalSum += stone;
}
int target = totalSum / 2;
vector<int> dp(target + 1);
for (int i = 1; i <= size; ++i) {
for (int j = target; j >= stones[i - 1]; --j) {
dp[j] = max(dp[j], stones[i - 1] + dp[j - stones[i - 1]]); // Maximize the sum of one subset
}
}
return totalSum - dp[target] * 2; // The difference between the two subsets
}
};
2.2 Unbounded Knapsack Problem
2.2.1 Unbounded Knapsack (Template)
Problem Link [Template] Unbounded Knapsack - Nowcoder (nowcoder.com)
Algorithm Principle In the unbounded knapsack, each item can be used multiple times. The state transition is adjusted to allow re - using the same item in subsequent weight capacities.
Code
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_SIZE = 1010;
int itemCount, capacity;
int weights[MAX_SIZE], values[MAX_SIZE];
int dpTable[MAX_SIZE][MAX_SIZE];
int main() {
// Read input
cin >> itemCount >> capacity;
for (int i = 1; i <= itemCount; ++i) {
cin >> weights[i] >> values[i];
}
// Solve the first sub - problem (max value, not necessarily full)
for (int i = 1; i <= itemCount; ++i) {
for (int j = 1; j <= capacity; ++j) {
dpTable[i][j] = dpTable[i - 1][j];
if (j >= weights[i]) {
dpTable[i][j] = max(dpTable[i][j], dpTable[i][j - weights[i]] + values[i]); // Can re - use the same item
}
}
}
cout << dpTable[itemCount][capacity] << endl;
// Solve the second sub - problem (max value, must be full)
memset(dpTable, 0, sizeof(dpTable));
for (int j = 1; j <= capacity; ++j) {
dpTable[0][j] = -1;
}
for (int i = 1; i <= itemCount; ++i) {
for (int j = 1; j <= capacity; ++j) {
dpTable[i][j] = dpTable[i - 1][j];
if (j >= weights[i] && dpTable[i][j - weights[i]] != -1) {
dpTable[i][j] = max(dpTable[i][j], dpTable[i][j - weights[i]] + values[i]);
}
}
}
cout << (dpTable[itemCount][capacity] == -1 ? 0 : dpTable[itemCount][capacity]) << endl;
}
// Space optimization
int optimizedDp[MAX_SIZE];
int main() {
// Read input...
// Solve the first sub - problem
for (int i = 1; i <= itemCount; ++i) {
for (int j = weights[i]; j <= capacity; ++j) { // Traverse from left to right (allow re - use)
optimizedDp[j] = max(optimizedDp[j], optimizedDp[j - weights[i]] + values[i]);
}
}
cout << optimizedDp[capacity] << endl;
// Solve the second sub - problem
memset(optimizedDp, 0, sizeof(optimizedDp));
for (int j = 1; j <= capacity; ++j) {
optimizedDp[j] = -1;
}
for (int i = 1; i <= itemCount; ++i) {
for (int j = weights[i]; j <= capacity; ++j) {
if (optimizedDp[j - weights[i]] != -1) {
optimizedDp[j] = max(optimizedDp[j], optimizedDp[j - weights[i]] + values[i]);
}
}
}
cout << (optimizedDp[capacity] == -1 ? 0 : optimizedDp[capacity]) << endl;
}
2.2.2 Coin Channge
Problem Link 322. Coin Change - LeetCode
Algorithm Principle We need to find the minimum number of coins to make a given amount. It's an unbounded knapsack problem where we minimize the count (instead of maximizing value). We use an infinite value (INF) to represent unachievable amounts to avoid incorrect minimum calculations.
Code
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
const int INF = 0x3f3f3f3f;
int size = coins.size();
vector<vector<int>> dp(size + 1, vector<int>(amount + 1));
for (int j = 1; j <= amount; ++j) {
dp[0][j] = INF; // No coins, can't make positive amounts
}
for (int i = 1; i <= size; ++i) {
for (int j = 1; j <= amount; ++j) {
dp[i][j] = dp[i - 1][j];
if (j >= coins[i - 1]) {
dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1); // Minimize coin count
}
}
}
return dp[size][amount] >= INF ? -1 : dp[size][amount];
}
};
// Space optimization
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
const int INF = 0x3f3f3f3f;
int size = coins.size();
vector<int> dp(amount + 1);
for (int j = 1; j <= amount; ++j) {
dp[j] = INF;
}
for (int i = 1; i <= size; ++i) {
for (int j = coins[i - 1]; j <= amount; ++j) {
dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);
}
}
return dp[amount] >= INF ? -1 : dp[amount];
}
};
2.2.3 Coin Change II
Problem Link 518. Coin Change II - LeetCode
Algorithm Principle We need to find the number of ways to make a given amount with coins (unbounded, as each coin can be used multiple times). The state transition accumulates the number of ways to form each amount.
Code
class Solution {
public:
int change(int amount, vector<int>& coins) {
int size = coins.size();
vector<int> dp(amount + 1);
dp[0] = 1; // One way to make amount 0 (no coins)
for (auto coin : coins) {
for (int j = coin; j <= amount; ++j) {
dp[j] += dp[j - coin]; // Accumulate ways
}
}
return dp[amount];
}
};
2.2.4 Perfect Squares
Problem Link 279. Perfect Squares - LeetCode
Algorithm Principle
We need to find the minimum number of perfect square numbers that sum to a given integer n. It's an unbounded knapsack problem where the "items" are perfect squares, and we minimize the count.
Code
class Solution {
public:
int numSquares(int n) {
int m = sqrt(n);
const int INF = 0x3f3f3f3f;
vector<int> dp(n + 1, INF);
dp[0] = 0; // Base case: 0 can be formed with 0 squares
for (int i = 1; i <= m; ++i) {
for (int j = i * i; j <= n; ++j) {
dp[j] = min(dp[j], dp[j - i * i] + 1); // Update with minimum count
}
}
return dp[n];
}
};
2.3 Two - Dimensional Cost Knapsack Problem
2.3.1 Ones and Zeroes
Problem Link 474. Ones and Zeroes - LeetCode
Algorithm Principle
We are given binary strings and need to find the maximum number of strings we can include with at most m 0s and n 1s. It's a 01 knapsack problem with two dimensions (count of 0s and 1s as constraints).
Code
// Three - dimensional dp table
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
int count = strs.size();
vector<vector<vector<int>>> dp(count + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));
for (int i = 1; i <= count; ++i) {
int c0 = countZeros(strs[i - 1]);
int c1 = strs[i - 1].size() - c0;
for (int j = 0; j <= m; ++j) {
for (int k = 0; k <= n; ++k) {
dp[i][j][k] = dp[i - 1][j][k]; // Do not select the i - th string
if (j >= c0 && k >= c1) { // Select the i - th string
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - c0][k - c1] + 1);
}
}
}
}
return dp[count][m][n];
}
int countZeros(const string& str) {
int cnt = 0;
for (auto ch : str) {
if (ch == '0') {
++cnt;
}
}
return cnt;
}
};
// Space optimization: Two - dimensional dp table
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
int count = strs.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 1; i <= count; ++i) {
int c0 = countZeros(strs[i - 1]);
int c1 = strs[i - 1].size() - c0;
for (int j = m; j >= c0; --j) { // Traverse from large to small to avoid overwriting
for (int k = n; k >= c1; --k) {
dp[j][k] = max(dp[j][k], dp[j - c0][k - c1] + 1);
}
}
}
return dp[m][n];
}
};
2.3.2 Profitable Schemes
Problem Link 879. Profitable Schemes - LeetCode
Algorithm Principle We need to find the number of profitable schemes with a given number of members and minimum profit. It's a two - dimensional cost knapsack (with group size and profit as constraints) where we count the number of valid schemes.
Code
// Three - dimensional dp table
class Solution {
public:
int profitableSchemes(int n, int m, vector<int>& group, vector<int>& profit) {
int count = group.size();
vector<vector<vector<int>>> dp(count + 1, vector<vector<int>>(n + 1, vector<int>(m + 1)));
for (int j = 0; j <= n; ++j) {
dp[0][j][0] = 1; // No plan, 0 profit, any number of members is valid
}
for (int i = 1; i <= count; ++i) {
for (int j = 0; j <= n; ++j) {
for (int k = 0; k <= m; ++k) {
dp[i][j][k] = dp[i - 1][j][k];
if (j >= group[i - 1]) {
// Handle negative profit index by taking max with 0
dp[i][j][k] += dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])];
dp[i][j][k] %= (int)1e9 + 7; // Modulo to prevent overflow
}
}
}
}
return dp[count][n][m];
}
};
// Space optimization: Two - dimensional dp table
class Solution {
public:
int profitableSchemes(int n, int m, vector<int>& group, vector<int>& profit) {
int count = group.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
for (int j = 0; j <= n; ++j) {
dp[j][0] = 1;
}
for (int i = 1; i <= count; ++i) {
for (int j = n; j >= group[i - 1]; --j) {
for (int k = m; k >= 0; --k) {
dp[j][k] += dp[j - group[i - 1]][max(0, k - profit[i - 1])];
dp[j][k] %= (int)1e9 + 7;
}
}
}
return dp[n][m];
}
};