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