AcWing 3. 完全背包问题

题目传送门

一、完全背包模板

把\(01\)背包的代码，容量循环的顺序变成由小到大即可。

#include 
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];


//完全背包问题
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++ )
        for (int j = v[i]; j <= m; j ++ ) //一个一个加上来，求一个最大值
            f[j] = max(f[j], f[j - v[i]] + w[i]); 
    cout << f[m] << endl;
    return 0;
}

二、01背包与完全背包的本质差别

状态表示：\(f(i,j)\)
集合： \(i\)是指在前\(i\)个物品中进行选择，\(j\)是指在总体积不超过\(j\)的容量下进行选择。
属性： 求一个最大值。 因为按上面的集合进行选择，每选择一次，就会出现一个结果，我们想求的是这些结果中的最大值。

状态计算
与\(01\)背包不一样，\(01\)背包是每一个物品选与不选，完全背包不是这个意思。是可以不选，选择\(1\)个，或者选择多个。

就是按选择\(0-k\)个物品，划分成了\(k+1\)个集合，原来两个选与不选，到这里就变成了\(k+1\)种方案，我们需要逐个讨论才能完整描述事实。

\(f(i,j)=max(f(i-1,j),f(i-1,j-v_i)+w_i,f(i-1,j-2*v_i)+2w_i,....\)

上面的公式简单理解一下，就是第\(i\)个物品
(1) 可以不取:\(f(i-1,j)\)
表示还在前\(i-1\)个物品中选择，第\(i\)个不参加选择，由于没有选择，所以空间还剩余\(j\)这么大。

(2) 选择1个:\(f(i-1,j-v_i)+w_i\)
表示选择了一个第\(i\)个物品，其它的都需要从前\(i-1\)个物品中选择，由于使用了一个\(i\)物品，所以袋子的容量减少\(v_i\),剩余 \(j-v_i\),同时，价值增加了\(w_i\).

(3) 选择\(2\)，\(3\)，\(4\)...都与选择\(1\)是一样的，一直到选择\(k+1\)个\(i\)号物品，使得体积大于了剩余容量，就不能继续了。

至此，我们已经得到了状态转移方程，是可以直接用来求解，方法就是三重循环，伪代码如下：

\(for(i=1;i<=n;i++)\) 物品
\(\qquad\) \(for(j=1;j<=m;j++)\) 体积
\(\qquad\) \(\qquad\) 在前\(i\)件物品的前提下，在\(j\)限定的空间里，遍历所有可有存在的个数
\(\qquad\) \(\qquad\) \(\qquad\) 求出最大值

这样做，需要三重循环，本题给出的\(n,m\)的取值范围是1000，三重循环的时间复杂度就是\(10^3 * 10^3 * 10^3=10^9\),而\(c++\)的一秒能计算\(10^7\)到\(10^8\),所以，会超时，需要继续优化。

那么如何进行优化呢？数学是个好东西，现在让数学大神出场：

已知：
\(f(i,j)=max(f(i-1,j),f(i-1,j-v_i)+w_i,f(i-1,j-2 \times v_i)+2w_i,....\)

如果\(j=j-v_i\)时，代入上式：

\(f(i,j-v_i)=max(f(i-1,j-v_i),f(i-1,j-2\times v_i)+w_i,f(i-1,j-3 \times v_i)+2w_i,....\)

新产生的式子，和第一个式子是很像的，但每项缺少一个\(w_i\),将新产生的式子代入最上面的式子：就是
$f(i,j-v_i)+w_i=max(f(i-1,j-v_i)+w_i,f(i-1,j-2\times v_i)+2 * w_i,f(i-1,j-3 \times v_i)+3 * w_i,.... $

\(f(i,j)=max(f(i-1,j),f(i,j-v_i)+w_i)\)

太神奇了！！一般同学们学习完全背包问题时，都喜欢直接看状态转移方程来理解含义，结果发现理解不上去。为什么会发生这样的事情呢？原因很简单，因为人家根本不是从现实直接过度到方程的，人家中间是有一顿推导过程的，你略过了中间过程，肯定看结果看不懂了，啥叫循序渐进？啥叫学个通透？要知其然，并知其所以然才能学的精通。

总结一下
二维情况下的状态转移方程

0 $\ $1背包 ： \(f[i][j]=max(f[i-1][j],f[i-1][j-v_i]+w_i)\)
完全背包： \(f[i][j]=max(f[i-1][j],f[i][j-v_i]+w_i)\)

这样，再用二维除一维的思路来思考，就得到了完全背包的终极解法：

 for (int i = 1; i <= n; i ++ )
        for (int j = v[i]; j <= m; j ++ ) 
            f[j] = max(f[j], f[j - v[i]] + w[i]); 

C++ 代码【二维朴素写法】

#include 
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N]; 
//枚举体积有限制是在优化后的算法有限制，在两维时候想怎么循环就怎么循环，是没有限制的
//为什么优化后要有限制呢？？
//这是因为在二维里，有一个是不是剩余容量能装得下当前物品的判断，在优化的版本去掉了这句话，把它放到循环条件中了。

//完全背包问题
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ ) {
            f[i][j] = f[i-1][j];
            if(j>=v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]); 
        }
    cout << f[n][m] << endl;
    return 0;
}

C++ 代码 【一维终极解法】

#include 
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];


//完全背包问题
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++ )
        for (int j = v[i]; j <= m; j ++ ) //一个一个加上来，求一个最大值
            f[j] = max(f[j], f[j - v[i]] + w[i]); 
    cout << f[m] << endl;
    return 0;
}

三、思考

为什么01背包要倒着推，完全背包要顺着推