初始不装装入物品时的二维表示：f[0][0],f[0][1],...,f[0][V]

两种问题的主要区别： 状态转移f[]的初始值不同。本题解主要讲解为什么要这样初始化。

问题一：背包至少能装多大价值的物品

背包可以不装满

由于背包可以不装满，所以初始f[i][j]的i=0,j=1~V时，不管背包暂时容量j的值是多少，当然背包里没有装入物品，背包中的总最大价值都是0。

memset(f1, 0, sizeof f1);

问题二：背包恰好装满时，能装多大价值的物品

背包必须恰好装够要求的容量

对于二维的f[i][j]：

当i=0,j=0时，没有装入物品，“装入”物品的总容量为0，同时，背包的真实容量j=0，所以初始化f[0][0]=0。

当i=0,j!=0时，没有装入物品，“装入”物品的总容量为0，不等于背包当前的真实容量j，因此此时的装法是不合法的，将这种不合法的装法初始赋值为-INF。

此后的状态转移过程中，假如背包没有恰好装满，即不合法，则当前f[i][j]的值是从初始的-INF转移而来，由于初始值是一个很小的负数，所以转移后依然是负数。

只有当背包刚好装入容量为j的物品时，f[i][j]的值是从f[0][0]逐渐转移得来，值为正数。

memset(f2, -0x3f, sizeof f2);

还不理解建议打表观察~

代码

#include<bits/stdc++.h>
using namespace std;
int f1[1010], f2[1010];
int n, m;
int main() {
    cin >> n >> m;
    memset(f1, 0, sizeof f1);
    memset(f2, -0x3f, sizeof f2);
    f2[0] = 0;
    for (int i = 1; i <= n; i ++) {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j --) {
            f1[j] = max(f1[j], f1[j - v] + w);
            f2[j] = max(f2[j], f2[j - v] + w);
        }
    }
    if (f2[m] < 0) f2[m] = 0;
    //f2[]内的下标取对应题目要求的恰好装的容量的值。此题取最大容量m
    cout << f1[m] << endl << f2[m] << endl;
    return 0;
}