完全背包例题（滚动数组）

1. 例题

题目

有N件物品和一个最多能背重量为 W 的背包。第 i ii 件物品的重量是w e i g h t [ i ] ,得到的价值是 v a l u e [ i ] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。同样leetcode上没有纯完全背包问题，都是需要完全背包的各种应用，需要转化成完全背包问题，所以我这里还是以纯完全背包问题进行讲解理论和原理。

在下面的讲解中，我依然举这个例子：

背包最大重量为4.

物品为：

每件商品都有无限个

问：背包能背的物品最大价值是多少？

思路

01背包和完全背包唯一不同在于遍历顺序上

01背包核心代码

for(int i = 0; i < weight.size(); i++)   // 遍历物品
{ 
  for(int j = bagWeight; j >= weight[i]; j--) // 遍历背包容量
  { 
    dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  }
}

01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次

举例：

假设物品0重量 w e i g h t [ 0 ] = 1，价值 v a l u e [ 0 ] = 15

如果是正序遍历

d p [ 1 ] = d p [ 1 − w e i g h t [ 0 ] ] + v a l u e [ 0 ] = 15

d p [ 2 ] = d p [ 2 − w e i g h t [ 0 ] ] + v a l u e [ 0 ] = 30

在第一行运行后 d p [ 1 ] dp[1]dp[1] 的状态已经发生改变，意味着已经放了物品0，而第二行运行后，叠加了改变后的 d p [ 1 ] dp[1]dp[1]，意味着物品0被放了两次。

那么为什么之前在写二维数组的时候是正序的？

因为我们实际求的是上一行的状态，也就是不放当前物品的情况，只不过在滚动数组中，压缩了状态。也即当前元素的公式被运行后，当前元素的状态（在当前行，包括物品0）覆盖了先前状态（在上一行，不含物品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]);
  }
}

遍历顺序是否强制先遍历物品，再遍历背包容量？

在01背包的一维数组中必须先遍历物品，再遍历背包容量。

而在完全背包的一维数组中，循环嵌套顺序却无所谓。

因为 dp[j] 是根据它同行的左边的元素推出来的，而无论哪种顺序，它的左值都是更新过的，可用的。

但先后顺序可以颠倒的前提是纯完全背包问题！题目变化的可能就不行

代码展示

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
void test_CompletePack()
{
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;
    vector<int> dp(bagWeight + 1);
    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];
}
int main()
{
    test_CompletePack();
    return 0;
}