苹果
时间限制:3000 ms | 内存限制:65535 KB
难度:3
- 描述
-
ctest有n个苹果,要将它放入容量为v的背包。给出第i个苹果的大小和价钱,求出能放入背包的苹果的总价钱最大值。
- 输入
- 有多组测试数据,每组测试数据第一行为2个正整数,分别代表苹果的个数n和背包的容量v,n、v同时为0时结束测试,此时不输出。接下来的n行,每行2个正整数,用空格隔开,分别代表苹果的大小c和价钱w。所有输入数字的范围大于等于0,小于等于1000。
- 输出
- 对每组测试数据输出一个整数,代表能放入背包的苹果的总价值。
- 样例输入
-
3 3 1 1 2 1 3 1 0 0
- 样例输出
-
2
经典0-1背包,使用动态规划方法解决。
可以将问题分解为对于每一个苹果是否放入的子问题,且对于第i个苹果(重量为C,价值为W),它与前i-1个有关。如果放入该苹果则比较放入苹果的耗费加上苹果的价值,何不放入苹果相比哪一个价值大。可得动态方程
dp[i][j]=max(dp[i-1][j], dp[i-1][j-c]+w);
如下是本题的二维数组实现
#include<stdio.h> #include<string.h> #define max(a, b) ( (a>b) ? a : b ) #define N 1005 int dp[N][N]; int main() { // freopen("289.txt", "r", stdin); int n,v,c,w,i,j; while( scanf("%d %d", &n,&v)!=EOF && (n || v) ) { memset(dp, 0, sizeof(dp)); for(i=1;i<=n;i++) { scanf("%d %d",&c, &w); for(j=1;j<c;j++) dp[i][j]=dp[i-1][j]; for(j=c; j<=v; j++) { dp[i][j]=max(dp[i-1][j], dp[i-1][j-c]+w); } } printf("%d\n",dp[n][v]); } return 0; }
一维数组实现
#include<stdio.h> #include<string.h> #define max(a, b) (a > b ? a : b ) int dp[1005]; int main() { // freopen("289.txt", "r", stdin); int n,v,c,w,i,j; while(scanf("%d %d", &n, &v)!=EOF && (n||v)) { memset(dp, 0, sizeof(dp)); for(j=0; j<n; j++) { scanf("%d %d",&c, &w); for(i=v; i>=c;i--) dp[i]=max(dp[i], dp[i-c]+w); } printf("%d\n", dp[v]); } return 0; }
参考文献:崔添翼《背包问题九讲》