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

2024-08-25 08:58

文章标签 问题背包寻宝记

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

小P寻宝记

Time Limit: 1000MS Memory limit: 65536K

题目描述

小P同学爱好探险寻宝，一天他去了伊利哇呀半岛发现了一批宝藏有n种，但不幸的是小P很懒，出门只带了一个容量为v的背包，所以注定他不能带走所有的宝藏。但是小P又很贪心想带走尽量多的宝藏。。。已知每种宝贝的重量pi与价值wi是不一样的，小P很笨，没有你聪明，但是聪明的你想到了好的解决方案了吗？

输入

输入数据有多组。

每组第一行有两个正整数n(n <= 10000)和v(v <= 10000)分别表示n种宝藏和包的体积。

接下来n行，每行有两个正整数pi， wi。

分别表示每种宝藏的体积pi （pi<=1000）,价值wi(wi<=1000)。

输出

小P所能带走的最多的宝藏。

示例输入

示例输出

提示

这是一个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  
 #include<stdio.h>  
 #include<string.h>  
   
   
 int maxa(int a,int b)  
 {  
     return a > b ? a : b;  
 }  
 int f[10009];  
 int main()  
 {  
     int p[10009];  
     int w[10009];  
     int i,j,k,nn,vv;  
     while(~scanf("%d%d",&nn,&vv))  
     {  
         memset (f,0,sizeof (f));  
         for(i = 1; i<=nn; i++)  
         {  
             scanf("%d%d",&p[i],&w[i]);  
         }  
           for (i = 1; i <= nn; i++)  
             for (k = vv; k >= 0; k--)  
             {  
                 if (k >= p[i])  
                     f[k] = maxa (f[k],f[k - p[i]] + w[i]);  
                 else  
                     f[k] = f[k];  
             }  
         printf ("%d\n",f[vv]);  
     }  
     return 0;  
 }  