0-1背包问题——小P寻宝记

本文主要是介绍0-1背包问题——小P寻宝记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

输入

输出

示例输入

4 6
1 4
2 6
3 12
2 7

示例输出

23

提示

这是一个0—1背包问题，从头开始遍历所给数据，i代表第几个数据，k代表包的容积，只要k大于物品所需要的体积，就比较加上这个物品的价值和不加上这个物品的价值谁打，并取最大值，若不大于这个体积，则取之前的值落下来，将k变为二维数组，则k的取值表如下所示（此表和此题目无关，只是形式相似）

因此，利用逆序循环就可以保证在计算f[v]时，公式f[v]=max{f[v],f[v-c[i]]+w[i]}中等号右边的f[v]和f[v-c[i]]+w[i]保存的是f[i-1][v]和f[i -1][v-c[i]]的值。

[html]  view plain copy

1. #include<stdio.h>  
2. #include<string.h>  
3.   
4.   
5. int maxa(int a,int b)  
6. {  
7.     return a > b ? a : b;  
8. }  
9. int f[10009];  
10. int main()  
11. {  
12.     int p[10009];  
13.     int w[10009];  
14.     int i,j,k,nn,vv;  
15.     while(~scanf("%d%d",&nn,&vv))  
16.     {  
17.         memset (f,0,sizeof (f));  
18.         for(i = 1; i<=nn; i++)  
19.         {  
20.             scanf("%d%d",&p[i],&w[i]);  
21.         }  
22.           for (i = 1; i <= nn; i++)  
23.             for (k = vv; k >= 0; k--)  
24.             {  
25.                 if (k >= p[i])  
26.                     f[k] = maxa (f[k],f[k - p[i]] + w[i]);  
27.                 else  
28.                     f[k] = f[k];  
29.             }  
30.         printf ("%d\n",f[vv]);  
31.     }  
32.     return 0;  
33. }  

这篇关于0-1背包问题——小P寻宝记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！