由于高数巨养的喵星人太傲娇了，要天天吃新鲜猫粮而且还经常欺负高数巨，所以高数巨决定买几条哈士奇尝尝鲜。这天高数巨来到了二手狗市场买哈士奇，高数巨看完了所有的哈士奇，记下了每条哈士奇的价格，并根据对它们的好感程度给它们每只都赋予了一个萌值。高数现在手里有X元，她想通过购买若干条哈士奇来获得尽可能多的萌值。现在给定高数巨手里的钱X以及N条哈士奇的价格和萌值，求高数巨最多可获得多少萌值
多组输入。
对于每组输入，第一行有两个整数N，X（1 < = N < = 100，1 < = X < = 1000），分别表示哈士奇的数量和高数巨的钱数
接下来的N行每行有两个整数Pi，Mi（1 < = Pi,Mi < = 100），分别表示第i条哈士奇的价格和萌值
对于每组数据，输出一个整数，表示高数巨最多可以获得的萌值，每组输出占一行
Input
2 100 50 20 60 40 3 100 20 55 20 35 90 95 1 10 20 50Output
40 95 0动态规划典型题目，相当于背包问题。
就本题而言，我们需要做的是建立一个dp二维数组，用来存放每一次输入价格和萌值之后进行比对的萌值，直到比对完最后一组，输出dp[n][x]即可。
核心代码：
for(int j=1;j<=x;j++) { dp[i][j]=(i==1?0:dp[i-1][j]); if(j>=p) { dp[i][j]=max(dp[i-1][j],dp[i-1][j-p]+m); } }拿题目中所给的数据进行举例促进理解。Sample Input 3 100，之后就会建立一个三行一百列的dp数组dp[3][100]（初值为0）；
之后input 20 55，由于这是第一个输入的数据组，所以i==1，所以从j=1，到j=20，dp[1][1~19]的值都为0，而当j遍历到20时，dp[1][20]=max(dp[0][20],dp[0][0]+55)，显然dp[1][20~100]都将等于55.
接着input 20 35，第二个输入的数据组，i==2，此时，i！=1，所以dp[2][1~19]的值都为dp[1][1~19]=0,当j遍历到20时，
dp[2][20]=max(dp[1][20],dp[1][0]+35)=55,dp[2][40]=max(dp[1][40],dp[1][20]+35)=55+35=90;此处取的是两个极限值，显然j-p，一个是j-p=0,j=20,和j-p=20,j=40每一组的极限值取决于上一次所输入的价格。所以，dp[2][20~39]=55,dp[2][40~100]=90。
到这一步，可以看出前两组数据所输入的萌值在两次的价格相加即20+20=40处开始进行类累加。
最后input 90 95，i==3，i！=1，dp[3][1~19]=dp[2][1~19]=0.dp[3][20~39]=55,dp[3][40~89]=90.(此处就是
dp[i][j]=(i==1?0:dp[i-1][j]语句的体现，作用是继承上次数据的值);再继续向后遍历，同上遍历，p=90,当j>=p时，即dp[3][90~100]=max(dp[2][90~100],dp[2][0~10]+m)=max(90,95)=95;
至此完成背包问题的求解，就是不断选取并继承上一次的萌值进行比较，进行分阶段的管理，动归的思想其实就是不断继承，不断地将新的一组数据与上一组数据比较，（在不超过界值的情况下）
AC代码：
#include<bits/stdc++.h> using namespace std; int max(int a,int b)//比较函数; { return a>b?a:b;//三目运算 } int main() { int n,x,p,m; while(cin>>n>>x){ int dp[110][1009]={0};//dp数组初始化 for(int i=1;i<=n;i++) { cin>>p>>m; for(int j=1;j<=x;j++)//j从1到所给的金额开始遍历 { dp[i][j]=(i==1?0:dp[i-1][j]);//继承上一行中的数据，进行数据的迁移 if(j>=p) { dp[i][j]=max(dp[i-1][j],dp[i-1][j-p]+m);//见上面解析 } } } cout<<dp[n][x]<<endl; } return 0; }================================================================================================
纯手打，理解了给个赞吧
