一、0-1 背包
题目解析
有一个背包，最多能容纳的体积是 V，有 n 个物品，体积为 v[i]，价值 w[i]。
- 问 1：最多能装的最大价值的物品？（背包不必装满）
- 问 2：背包恰好装满，最多能装多大价值的物品
算法原理
第一问
-
状态表示
- dp[i][j]：从前 i 个物品中挑选，总体积不超过 j，所有选法中能挑选出来的最大价值。
-
状态转移方程
- 不选 i 物品：dp[i-1][j]
- 选 i 物品：w[i] + dp[i-1][j-v[i]] (需满足 j >= v[i])
- 综合：
dp[i][j] = max(dp[i-1][j], w[i] + dp[i-1][j-v[i]])
-
初始化
- 容量不超过 0 或物品为 0 时，价值为 0。
-
填表顺序
- 从上往下，从左往右。
-
返回值
dp[n][v]
第二问（恰好装满）
- 状态表示
- dp[i][j]：从前 i 个物品中挑选，总体积等于 j，所有选法中能挑选出来的最大价值。
- 状态转移方程
- 需判断
dp[i-1][j-v[i]] != -1。
- 需判断
- 初始化
dp[0][0] = 0，其余dp[0][j] = -1。
代码编写
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, v;
cin >> n >> v;
vector<int> vl(n + 1), wl(n + 1);
vector<vector<int>> dp1(n + 1, vector<int>(v + 1));
vector<vector<int>> dp2(n + 1, vector<int>(v + 1));
for (int i = 1; i <= n; i++) {
int tv, tw;
cin >> tv >> tw;
vl[i] = tv;
wl[i] = tw;
}
// 初始化第二问（恰好装满）
for (int i = 1; i <= v; i++) dp2[0][i] = -1;
// DP 表填写
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= v; j++) {
// 第一问
if (j - vl[i] >= 0)
dp1[i][j] = max(dp1[i - 1][j], wl[i] + dp1[i - 1][j - vl[i]]);
else
dp1[i][j] = dp1[i - 1][j];
// 第二问
if (j - vl[i] >= 0 && dp2[i - 1][j - vl[i]] != -1)
dp2[i][j] = max(dp2[i - 1][j], wl[i] + dp2[i - 1][j - vl[i]]);
else
dp2[i][j] = dp2[i - 1][j];
}
}
cout << dp1[n][v] << endl;
if (dp2[n][v] == -1) cout << 0;
else cout << dp2[n][v];
return 0;
}
空间优化
使用一维数组从后往前遍历：
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, v;
cin >> n >> v;
vector<int> vl(n + 1), dp1(v + 1);
vector<int> dp2(v + 1);
for (int i = 1; i <= n; i++) {
int tv, tw;
cin >> tv >> tw;
vl[i] = tv;
// wl 逻辑内联处理
}
for (int i = 1; i <= v; i++) dp2[i] = -1;
for (int i = 1; i <= n; i++) {
int tv, tw;
// 此处简化演示，实际需读取输入
// 假设已读取 vl[i], wl[i]
for (int j = v; j >= vl[i]; j--) {
dp1[j] = max(dp1[j], wl[i] + dp1[j - vl[i]]);
if (dp2[j - vl[i]] != -1)
dp2[j] = max(dp2[j], wl[i] + dp2[j - vl[i]]);
}
}
cout << dp1[v] << endl;
if (dp2[v] == -1) cout << 0;
else cout << dp2[v];
return ;
}
例题：分割等和子集
将数组分割为两个子集，使得两个子集的元素和相等。转化为能否抽出部分元素使和为 sum/2。
class Solution {
public boolean canPartition(int[] nums) {
int n = nums.length, sum = 0;
for (int num : nums) sum += num;
if (sum % 2 != 0) return false;
boolean[] dp = new boolean[sum / 2 + 1];
dp[0] = true;
for (int num : nums) {
for (int j = sum / 2; j >= num; j--) {
dp[j] = dp[j] || dp[j - num];
}
}
return dp[sum / 2];
}
}
二、完全背包
每件物品可以选无限次。与 0-1 背包的区别在于状态转移方程和遍历顺序。
算法原理
- 状态表示
- dp[i][j]：从前 i 个物品中选，总体积不超过 j，最大价值。
- 状态转移方程
dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i])- 注意：这里使用的是当前行
dp[i][j-v[i]]，而非上一行。
- 填表顺序
- 从上往下，从左往右（正序遍历）。
代码编写
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> v(n), w(n);
for (int i = 0; i < n; i++) cin >> v[i] >> w[i];
vector<int> dp(m + 1);
// 若要求恰好装满，需初始化为负无穷
for (int i = 0; i < n; i++) {
for (int j = v[i]; j <= m; j++) {
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << dp[m] << endl;
return 0;
}
三、二维费用背包
限制条件增加至两个维度（如人数和利润）。
例题：盈利计划
给定任务列表，每个任务有人数消耗和利润。求总人数不超过 n 且总利润至少为 minProfit 的方案数。
算法原理
- 状态表示
- dp[i][j][k]：前 i 个任务，人数不超过 j，利润至少为 k 的方案数。
- 状态转移方程
dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-group[i]][max(0, k-profit[i])]
- 初始化
dp[0][j][0] = 1。
代码编写
class Solution {
public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
int m = group.length;
int[][] dp = new int[n + 1][minProfit + 1];
for (int j = 0; j <= n; j++) dp[j][0] = 1;
for (int i = 1; i <= m; i++) {
for (int j = n; j >= group[i - 1]; j--) {
for (int k = minProfit; k >= 0; k--) {
dp[j][k] = (dp[j][k] + dp[j - group[i - 1]][Math.max(0, k - profit[i - 1])]) % 1000000007;
}
}
}
return dp[n][minProfit];
}
}
四、似包非包
例题：组合总和 IV
求排列数，元素可重复选取，顺序不同视为不同方案。
算法原理
- 状态表示
- dp[i]：凑成总和为 i 的排列数。
- 状态转移方程
dp[i] = sum(dp[i - num])for num in nums
- 填表顺序
- 外层循环 target，内层循环 nums（先遍历目标值，体现排列）。
代码编写
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int num : nums) {
if (num <= i) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
}
