【背包dp----01背包】例题三------（标准的01背包+变种01背包1【恰好装满背包体积 产生的 最大价值】）
【模板】01背包 题目链接
题目描述 :
输入描述:
输出描述:
示例1
输入
3 5
2 10
4 5
1 4
输出
14
9
说明
装第一个和第三个物品时总价值最大，但是装第二个和第三个物品可以使得背包恰好装满且总价值最大。
示例2
输入
3 8
12 6
11 8
6 8
输出
8
0
说明
装第三个物品时总价值最大但是不满，装满背包无解。
备注:
要求O(nV)的时间复杂度，O(V)空间复杂度
题目描述
给定 n 个物品，每个物品有体积 v[i] 和价值 m[i]。一个容量为 vs 的背包。
你可以选择一些物品放入背包中，使得总体积 不超过或恰好等于 背包容量，目标是使总价值最大。
一、 DP 状态定义
dp[i][j] 表示前 i 个物品中选择若干物品，装入容量为 j 的背包中可以获得的最大价值。
这个状态定义允许容量 j 不超过 当前背包容量，不要求填满。
二、状态转移方程
对于每个物品 i 和容量 j：
- 如果当前物品可以放进容量
j的背包中（即j >= v[i]），那么有两种选择：- 不选这个物品：
dp[i][j] = dp[i-1][j] - 选这个物品：
dp[i][j] = max(dp[i][j], dp[i-1][j - v[i]] + m[i])
- 不选这个物品：
否则：
- 只能不选：
dp[i][j] = dp[i-1][j]
三、初始化方式
vector<vector<ll>> dp(n+1, vector<ll>(vs+1, INT_MIN));
dp[0][0] = 0;
- 初始状态只有
dp[0][0] = 0，表示没有物品、容量为 0 时合法； - 其他所有状态初始化为
INT_MIN（极小值），表示不可达； - 这样在后续转移过程中，只保留有效路径的状态。
四、输出策略
✅ 不要求填满的情况下的最大价值（ender1）：
ll ender1 = INT_MIN;
for (ll i = vs; i >= 1; i--) {ender1 = max(ender1, dp[n][i]);
}
ender1 = (ender1 < 0) ? 0 : ender1;
- 遍历
dp[n][1...vs]，找出最大值； - 如果所有值都为负数，则说明没有任何合法组合，返回 0。
✅ 必须恰好填满容量 vs 的情况（ender2）：
ll ender2 = (dp[n][vs] < 0) ? 0 : dp[n][vs];
- 直接取
dp[n][vs]； - 如果它是负数，说明无法恰好填满容量
vs，返回 0。
五、易错点总结
| 易错点 | 原因 | 解决方法 |
|---|---|---|
❗ 忽略 j=0 的遍历 | 容量 j=0 是合法状态，必须包含在内 | 内层循环从 j=0 开始 |
| ❗ 初始化错误 | 若将 dp 初始化为 0，会导致无法区分是否可达 | 使用 INT_MIN 表示不可达 |
| ❗ 忘记处理负值 | 若最终结果为负，说明无合法组合 | 加上 (val < 0) ? 0 : val 处理 |
❗ 不理解 ender1 和 ender2 区别 | 一个是“任意容量下”的最大值，一个是“特定容量”下的最大值 | 分开处理即可 |
六、完整代码
#include<bits/stdc++.h>
using ll = long long;
using namespace std;int main()
{ll n, vs;cin >> n >> vs;vector<ll> m(n + 1, 0);vector<ll> v(n + 1, 0);for (ll i = 1; i <= n; ++i)cin >> v[i] >> m[i];// 初始化 dp 数组vector<vector<ll>> dp(n + 1, vector<ll>(vs + 1, INT_MIN));dp[0][0] = 0;for (ll i = 1; i <= n; i++) {for (ll j = 0; j <= vs; j++) {if (j >= v[i])dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + m[i]);elsedp[i][j] = dp[i - 1][j];}}// 不要求填满的最大价值ll ender1 = INT_MIN;for (ll i = vs; i >= 1; i--){ender1 = max(ender1, dp[n][i]);}ender1 = (ender1 < 0) ? 0 : ender1;// 恰好填满的最大价值ll ender2 = (dp[n][vs] < 0) ? 0 : dp[n][vs];cout << ender1 << endl << ender2;return 0;
}
想从（1,1）开始转移的话
必须显式初始化dp[n][0]=0;
代码如下：
#include<bits/stdc++.h>
using ll = long long;
using namespace std;int main()
{ll n, vs;cin >> n >> vs;vector<ll>m(n + 1, 0);vector<ll>v(n + 1, 0);for (ll i = 1; i <= n; i++){cin >> v[i] >> m[i];}//原问题：这个背包至多能装多大价值的物品//抽象成 前n个物品（经过选择）装满体积为vs的背包 能获得的最大价值//dp[i][j]表示 前i个物品（经过选择）装满体积为vs的背包,能获得的最大价值//状态转移方程：(每个位置的元素都有选 或 不选 两种状态)//dp[i][j]=max(dp[i-1][j](不选), dp[i-1][j-v[i]]+m[i])(选)//注意体积问题：体积j>=v[i]时，才能选择当前物品vector<vector<ll>>dp(n + 1, vector<ll>(vs + 1, INT_MIN));//显式初始化 前n件物品 （经过选择） 装满体积为0的背包，能获得的最大价值为0for (ll i = 0; i <= n; i++){dp[i][0] = 0;}for (ll i = 1; i <= n; i++){for (ll j = 1; j <= vs; j++){if (j >= v[i]){dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + m[i]);}else{dp[i][j] = dp[i - 1][j];}}}//最大价值应该是最后一行：前n个物品 放满 体积为j的最大价值（找最大的）//dp[n][vs]应该是填满体积为vs时 创造的最大价值ll ender1 = INT_MIN;for (ll i = vs; i >= 1; i--){ender1 = max(ender1, dp[n][i]);}ender1 = (ender1 < 0) ? 0 : ender1;ll ender2 = (dp[n][vs] < 0) ? 0 : dp[n][vs];//cout<<dp[n][vs]<<endl;cout << ender1 << endl << ender2;return 0;
}