动态规划09-完全背包

问题描述

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

思路分析

跟01背包每个物品智能装一次不同，在完全背包的情况下物品数量没有限制，因此，回想起之前叙述过的滚动数组，内层循环遍历背包的时候要从后向前遍历就是为了防止重复计数，在本题的情况中就是要有重复计数，因此采用顺序遍历。

1. 确定dp数组含义：dp[j]的含义就是当背包的容量是j的时候物品的价值最大值。
2. 确定动态规划状态转移方程：dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
3. 确定遍历顺序：外层循环遍历物品，从前向后遍历；内层循环遍历背包，从当前重量开始向后顺序遍历一直到背包容量。
4. 初始化dp数组：一开始将dp数组全部初始化为0即可
5. 代入数据验证

代码

// 先遍历物品，在遍历背包
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;
}