完全背包是01背包的进阶版。在这里补充一下代码随想录的完全背包状态转移式的推导。有兴趣的可以先看一看原版。
- 状态转移方程
状态:dp[i][j] 选择前i个物品,容量为j的背包时 所选物品价值总和最大。
状态转移:
dp[i][j]=max(dp[i-1][j-k* v[i]]+k* w[i]) (k=0,1,2,3...) (j-k* v[i]>0) - 方程优化
dp[i][j]=max(dp[i-1][j],dp[i-1][j- v[i]]+ w[i],dp[i-1][j- 2* v[i]]+ 2* w[i],....) --->(1)
dp[i][j-v[i]]=max(dp[i-1][j-v[i]],dp[i-1][j- 2* v[i]]+ w[i],dp[i-1][j- 3* v[i]]+ 2* w[i],....)
dp[i][j-v[i]]+w[i]=max(dp[i-1][j-v[i]]+w[i],dp[i-1][j- 2* v[i]]+ 2 * w[i],dp[i-1][j- 3* v[i]]+ 3* w[i],....) --->(2)
结合(1)(2)可得:
dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i]);
- 代码:
// 先遍历物品,在遍历背包
void test_CompletePack() {
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;
vector<int> dp(bagWeight + 1, 0);
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[bagWeight] << endl;
}
int main() {