C++完全背包问题，oj平台答案对50%

题目描述
完全背包定义有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。本题要求是背包恰好装满背包时，求出最大价值总和是多少。如果不能恰好装满背包，输出NO
输入
第一行： N 表示有多少组测试数据（N<7）。
接下来每组测试数据的第一行有两个整数M，V。 M表示物品种类的数目，V表示背包的总容量。(0<M<=2000，0<V<=50000)
接下来的M行每行有两个整数c，w分别表示每种物品的重量和价值(0<c<100000，0<w<100000)
输出
对应每组测试数据输出结果（如果能恰好装满背包，输出装满背包时背包内物品的最大价值总和。 如果不能恰好装满背包，输出NO）
样例输入
2
1 5
2 2
2 5
2 2
5 1
样例输出
NO
1


#include<iostream>  
#include<stdio.h>  
#include<string>  
#include<cstring>  
        using namespace std;  
    int f[50010], c[2010], w[2010];  
    int main()  
    {  
        int test, m, v, i, j;  
        scanf("%d", &test);  
        while (test--)  
        {  
            memset(f, -10000000, sizeof(f)); 
            f[0] = 0;  
            scanf("%d%d", &m, &v);  
            for (i = 1; i <= m; ++i)  
                scanf("%d%d", &c[i], &w[i]);  
            for (i = 1; i <= m; ++i)  
            for (j = 0; j <= v; ++j)
            if (j >= c[i])  
                f[j] = f[j]>(f[j - c[i]] + w[i]) ? f[j] : f[j - c[i]] + w[i]; 
            if (f[v]<0) 
                printf("NO\n");  
            else  
                printf("%d\n", f[v]);  
        }  
    }

引用chatGPT作答，这是一个动态规划问题，可以使用二维数组或者滚动数组进行实现。但是由于物品数目较多，使用二维数组空间复杂度过高，因此使用滚动数组的方式，将二维数组转化为一维数组。具体来说，定义$f[j]$表示恰好装满容量为$j$的背包可以得到的最大价值，初始化为$0$，然后遍历每一个物品，对于每一个物品，都考虑是否选择该物品，如果选择该物品，则状态转移方程为$f[j]=max(f[j],f[j-c[i]]+w[i])$。如果不选择该物品，则状态转移方程为$f[j]=f[j]$。在遍历完所有的物品之后，如果$f[v]<0$，则输出"NO"，否则输出$f[v]$。

以下是对于给出代码的一些补充说明：

对于$f$数组的初始化，不能将其初始化为$0$，因为物品的价值可以为负数，如果将$f$数组初始化为$0$，则有可能会将一个价值为负数的物品加入到背包中，这是不符合题目要求的。因此，需要将$f$数组初始化为一个极小值，例如$-10^7$。

遍历$j$的时候，应该从$0$开始，这样才能保证背包能够恰好装满。

遍历$i$的时候，应该从$1$开始，因为第$0$个物品没有体积和价值，没有任何意义。

对于状态转移方程$f[j]=max(f[j],f[j-c[i]]+w[i])$，应该首先判断$j>=c[i]$，只有当$j>=c[i]$的时候才能使用状态转移方程，否则会访问$f[-1]$，导致运行错误。

输出结果的时候，应该先判断$f[v]$是否小于$0$，如果小于$0$，则输出"NO"，否则输出$f[v]$。

以下是修改过的代码：

#include<iostream>  
#include<cstring>  
using namespace std;  

const int MAXN = 2010;
const int MAXV = 50010;
int f[MAXV];
int c[MAXN], w[MAXN];

int main() {
    int test;
    scanf("%d", &test);  

    while (test--) {
        int m, v;
        scanf("%d%d", &m, &v);
        for (int i = 1; i <= m; ++i) {
            scanf("%d%d", &c[i], &w[i]);
        }

        memset(f, -0x3f, sizeof(f));
        f[0] = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = c[i]; j <= v; ++j) {
                f[j] = max(f[j], f[j - c[i]] + w[i]);
            }
        }

        if (f[v] < 0) {
            printf("NO\n");
        } else {
            printf("%d\n", f[v]);
        }
    }

    return 0;
}

引用chatgpt部分指引作答：
运行结果如下：

img

这个问题可以使用动态规划来解决。我们可以定义一个二维数组 $f[i][j]$，表示前 $i$ 种物品，背包容量为 $j$ 时的最大价值。对于第 $i$ 种物品，我们可以选择不装入，或者选择装入若干件。如果选择不装入，则 $f[i][j]=f[i-1][j]$；如果选择装入 $k$ 件，则 $f[i][j]=f[i-1][j-kc_i]+kw_i$，其中 $c_i$ 表示第 $i$ 种物品的体积，$w_i$ 表示第 $i$ 种物品的价值。因为每种物品都可以选择无限件，所以 $k$ 的范围是 $0 \leq k \leq \lfloor \frac{j}{c_i} \rfloor$。

根据以上状态转移方程，我们可以使用一维数组 $f[j]$ 来优化空间，因为 $f[i][j]$ 只依赖于 $f[i-1][j]$ 和 $f[i][j-c_i]$。

最终的答案是 $f[v]$，即背包容量为 $v$ 时的最大价值。如果 $f[v]<0$，则说明不能恰好装满背包，输出 "NO"；否则输出 $f[v]$。

以下是 C++ 的代码实现：

#include <iostream>
#include <cstring>
#include<algorithm>

using namespace std;

const int MAX_M = 2000;
const int MAX_V = 50000;

int f[MAX_V + 1];
int c[MAX_M + 1];
int w[MAX_M + 1];

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int m, v;
        cin >> m >> v;
        for (int i = 1; i <= m; i++)
            cin >> c[i] >> w[i];
        memset(f, -0x3f, sizeof(f));
        f[0] = 0;
        for (int i = 1; i <= m; i++)
            for (int j = c[i]; j <= v; j++)
                f[j] = max(f[j], f[j - c[i]] + w[i]);
        if (f[v] < 0)
            cout << "NO" << endl;
        else
            cout << f[v] << endl;
    }
    return 0;
}

这里将数组 $f$ 的初始化值设为 $-0x3f$，因为 $f$ 中的元素可能会取到负数，如果初始化为 $0$，则无法判断背包是否能够恰好装满。