-
Problem Description
- 直接说题意，完全背包定义有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。本题要求是背包恰好装满背包时，求出最大价值总和是多少。如果不能恰好装满背包，输出NO Input
- 第一行： N 表示有多少组测试数据（N<7）。接下来每组测试数据的第一行有两个整数M，V。 M表示物品种类的数目，V表示背包的总容量。(0<M<=2000，0<V<=50000)接下来的M行每行有两个整数c，w分别表示每种物品的重量和价值(0<c<100000，0<w<100000) Output
- 对应每组测试数据输出结果（如果能恰好装满背包，输出装满背包时背包内物品的最大价值总和。 如果不能恰好装满背包，输出NO） Sample Input
-
2 1 5 2 2 2 5 2 2 5 1
Sample Output
-
NO 1
题目思路
-
完全背包问题，完全背包不同于01背包的地方是物品有无限个。一般的完全背包问题会问在一定容量背包中所能达到的最大价值。这道题目要求的虽然也是背包中的最大价值，但是有一个前提是背包被装满。可以肯定的是，当背包中物品达到最大价值时，背包不一定装满。而背包装满也不一定是最大价值。这里用到了一个技巧。初始化dp[0] 为0，其余都为较大的负数。dp[j]表示的是背包容量为j时，能达到的最大价值（前提是背包装满）。状态转移方程还是一样的dp[j] = max(dp[j],dp[j-v[i]]+w[i])，试想，如果该背包能被装满，即j-v[i] = k*v[i]（0<=k<=c/v[i]） 。由状态转移方程的方向，我们可以确定能装满的背包的价值都不为负数。举个例子题目中的
体积 价值
物品1: 2 2
物品2: 5 1
dp[0] = 0;
dp[2] = max(dp[2], dp[2-2]+2) = 2; dp[3] = max(dp[3], dp[3-2]+2) = -inf+2; dp[4] = max(dp[4], dp[4-2]+2) = 4; dp[5] = -inf+4
dp[5] = max(dp[5], dp[5-5]+1) = 1;
因此，如果能装满，那么我们所求出的数一定是非负数。否则无法装满，则输出NO。
-
题目代码
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
int n, v, N;
int c[2005], w[2005];
int dp[50005];
int main(){scanf("%d",&N);while(N--){scanf("%d%d",&n,&v);for(int i = 0; i <= 50005; i++) dp[i] = -1000000;dp[0] = 0; // 注意这里 for(int i = 0; i < n; i++){scanf("%d%d",&c[i],&w[i]);} for(int i = 0; i < n; i++){for(int j = c[i]; j <= v; j++){dp[j] = max(dp[j], dp[j-c[i]]+w[i]);}}if(dp[v] < 0)puts("NO");elseprintf("%d\n",dp[v]);}return 0;
}