全然背包
时间限制：
3000 ms | 内存限制：
65535 KB
难度：
4
- 描写叙述
-
直接说题意，全然背包定义有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<stdio.h> #include<string.h> #include<algorithm> using namespace std; int main() { int test,n,v,i,j,t,sum; int a[50010],b[50010],dp[50010]; scanf("%d",&test); while(test--) { scanf("%d %d",&n,&v); for(i=1;i<=n;i++) { scanf("%d %d",&a[i],&b[i]); } memset(dp,-100,sizeof(dp)); dp[0]=0; for(i=1;i<=n;i++) { for(j=a[i];j<=v;j++) //与01背包问题循环顺序恰好相反。 if(dp[j]<dp[j-a[i]]+b[i]) dp[j]=dp[j-a[i]]+b[i]; } if(dp[v]<0) printf("NO\n"); else printf("%d\n",dp[v]); } return 0; }
版权声明：本文博主原创文章。博客，未经同意不得转载。