题目1364：v字仇杀队

 v整整策划了一年炸掉英国政府的大楼来推翻独裁统治，在这期间，v遇到了一个问题：如何使用有限的炸弹来达到最大的破坏力。

         看过电影的人都知道，v最后使用自己偷偷建造的一个装满炸药的地铁直接开向国会大厦。虽然v的炸药很多，但是地铁中能装载的炸药数是有限的，因此，v就要挑选一部分炸药。如果换作你，你能在地铁有限的空间中装载挑选出来的炸药使得地铁的破坏力最大吗？ 

输入：

         每组测试数据可能有多组输入，对于每一组输入，

         输入的第一行包括两个整数S(1 <= S <= 1000)和C(1<=C<=100)，S代表地铁的总空间的大小，C代表v一共存储的炸药的个数。

         接下来的C行每行包括两个1到100(包括1和100)的整数，分别表示这个炸药所需要的空间以及它所能产生的破坏力。

输出：

         对于每组输入，输出只包括一行，这一行只包含一个整数，表示在地铁的有限的空间里转载选出的炸药，能产生的最大的破坏力。如果每个炸药的体积都很大，地铁的空间连一个炸药都装不下，输出0即可。

样例输入：

70 371 10069 11 2

样例输出：

3

算法分析

       背包问题，用动态规划解决 可以参见  九度笔记之 1209最小邮票数

       类似的题目还有 

源程序

        

//============================================================================
// Name        : judo1364.cpp
// Author      : wdy
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
//similar to 1462
//similar t0 1455
//similar to 1364
#include <iostream>
using namespace std;
void v(int S,int n){int *dp = new int[S+1];for(int i = 0;i<S+1;i++){dp[i]= 0 ;}int space=0;int power=0;for(int i = 0;i<n;i++){std::cin>>space>>power;for(int j = S;j>=space;j--){//must decreassdp[j] = std::max(dp[j],dp[j-space]+power);}}std::cout<<dp[S]<<std::endl;
}void judo(){int n;int s;while(std::cin>>s>>n){v(s,n);}}
int main() {//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!judo();return 0;
}/**************************************************************Problem: 1364User: KESLanguage: C++Result: AcceptedTime:260 msMemory:1784 kb
****************************************************************/