115
九度题目1364：v字仇杀队
题目1364：v字仇杀队时间限制：1 秒内存限制：32 兆特殊判题：否提交：392解决：161
题目描述：
最近玄影游侠看了一部非常好看的电影，叫做《v字仇杀队》。下面是这部电影的主角v：
它想说明的一个问题就是，你现在所想的真的是你自己内心所想的吗？还是别人，社会让你这么想的？你要有自己的想法，每个人内心都有自己的准则，你没有必要按照大众的准则去想。
v整整策划了一年炸掉英国政府的大楼来推翻独裁统治，在这期间，v遇到了一个问题：如何使用有限的炸弹来达到最大的破坏力。
看过电影的人都知道，v最后使用自己偷偷建造的一个装满炸药的地铁直接开向国会大厦。虽然v的炸药很多，但是地铁中能装载的炸药数是有限的，因此，v就要挑选一部分炸药。如果换作你，你能在地铁有限的空间中装载挑选出来的炸药使得地铁的破坏力最大吗？
输入：
每组测试数据可能有多组输入，对于每一组输入，
输入的第一行包括两个整数S(1 <= S <= 1000)和C(1<=C<=100)，S代表地铁的总空间的大小，C代表v一共存储的炸药的个数。
接下来的C行每行包括两个1到100(包括1和100)的整数，分别表示这个炸药所需要的空间以及它所能产生的破坏力。
输出：
对于每组输入，输出只包括一行，这一行只包含一个整数，表示在地铁的有限的空间里转载选出的炸药，能产生的最大的破坏力。如果每个炸药的体积都很大，地铁的空间连一个炸药都装不下，输出0即可。
样例输入：
70 3
71 100
69 1
1 2
样例输出：
3
典型的01背包
AC代码：
#include<stdio.h>
#include<string.h>
int w[120],v[120],dp[1500];
int max(int a,int b)
{return a>b?a:b;}
int OneZeroPack(int n,int m)
{
int i,j;
for(i=0;i<m;i++)
for(j=n;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
return dp[n];
}
int main()
{
int i,j,n,m,num;
while(scanf("%d %d",&n,&m)!=EOF)
{
for(i=0;i<m;i++)
scanf("%d %d",&w[i],&v[i]);
memset(dp,0,sizeof(dp));
num=OneZeroPack(n,m);
if(num>0)
printf("%d\n",num);
else
printf("0\n");
}
return 0;
}
最后更新：2017-04-03 12:56:41