做完AcWing 1020.潜水员这个题后对问题有了新的认识.Update
下面以01背包为例
1. 体积恰好为背包体积的最大价值
状态表示为dp[j] 体积恰好为j时能取得的最大价值
dp[0] = 0;dp[1-i] = -INF;
如果循环结束后dp[V] = -INF,则无法恰好装满
分析:
状态转移方程为:
dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
dp[0] = 0 当放入第一件物品时 只有dp[v[1]] = 0+w[1] ,
其余体积dp[j] = -INF+w[1] = -INF;
同理放入第二,第三件物品时 只有当前体积恰好放入当前物品的时候才会呈现出正值(dp[w[1]+w[2]+…]),
其他体积都被-INF覆盖掉 因此如果V不能恰好装满 最后会得到负无穷。
//此处提到的-INF并不是真正的负无穷,只是一个数据范围内绝对值相对较大的负数。
2. 体积恰好为背包体积
状态表示为dp[j] 体积恰好为j时能取得的最小价值
dp[0] = 0;dp[1-i] = INF;
如果最后dp[V] == INF ,则无法恰好装满
分析:
状态转移方程为:
dp[j] = min(dp[j], dp[j-v[i]]+w[i]) ;
同理只有恰好装满(即比0刚好多v[i]的组合总和)时最小值才能取到正常值 否则取min时会被INF覆盖
总结:
条件控制j>=v[i] 因为体积不可能恰好为负数
恰好装满取最大值:
dp数组初始化为负无穷 dp[0] = 0;dp[V]取负值则无法恰好装满.
恰好装满取最小值:
dp数组初始化为正无穷 dp[0] = 0;dp[V] == INF 则无法刚好装满.
3.至多为背包体积
状态表示为dp[j] 体积最多为j时能取得的最大价值
memset(dp,0,sizeof dp);
这个问题其实就是最常见的01背包问题
条件控制 j>=v[i] 因为体积不可能至少为负数
4.至少为背包体积
状态表示为dp[j] 体积至少为j时所能取得的最大价值
dp[0] = 0;dp[1-i] = INF/-INF(求最小值/求最大值)
条件控制j >=0 即j-v[i] 可以为负数
当j - v[i] < 0时,意味着所装物品体积超过了当前体积j,满足“体积至少为j”这个条件
特殊判定一下{
t = j - v[i];
if(t < 0)t = 0;
dp[j] = max(dp[j],dp[t] + w[i]);
}