qq_51370411 2023-04-23 02:30 采纳率: 75%
浏览 53
已结题

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]);  
        }  
    }  
  • 写回答

3条回答 默认 最新

  • Zyb0627 2023-04-23 09:07
    关注

    引用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;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

问题事件

  • 系统已结题 5月1日
  • 已采纳回答 4月23日
  • 修改了问题 4月23日
  • 创建了问题 4月23日