题目
Problem Description
由于高数巨养的喵星人太傲娇了，要天天吃新鲜猫粮而且还经常欺负高数巨，所以高数巨决定买几条哈士奇尝尝鲜。这天高数巨来到了二手狗市场买哈士奇，高数巨看完了所有的哈士奇，记下了每条哈士奇的价格，并根据对它们的好感程度给它们每只都赋予了一个萌值。高数现在手里有X元，她想通过购买若干条哈士奇来获得尽可能多的萌值。现在给定高数巨手里的钱X以及N条哈士奇的价格和萌值，求高数巨最多可获得多少萌值
Input
多组输入。
对于每组输入，第一行有两个整数N，X（1 < = N < = 100，1 < = X < = 1000），分别表示哈士奇的数量和高数巨的钱数
接下来的N行每行有两个整数Pi，Mi（1 < = Pi,Mi < = 100），分别表示第i条哈士奇的价格和萌值
Output
对于每组数据，输出一个整数，表示高数巨最多可以获得的萌值，每组输出占一行
Sample Input
2 100
50 20
60 40
3 100
20 55
20 35
90 95
1 10
20 50
Sample Output
40
95
0
分析
一道基础的动态规划题目，首先建立数组，我这里建立的是二维数组，（比较好理解一些，也可以建立一维数组的），N * M 的数组，N为狗的数量，M为钱数，我们从钱数为1开始按狗的数目从1到N来走整个数组，关键在于，对于一个确定的钱数 i ，如果大于某一只狗的价钱，那么我们就有两种选择，要么买，要么不买，买的话就相当于当前的前述-这只狗的价钱对应的值加上这只狗的萌值。。。这个看代码会比较好理解一些。。。
代码
#include<stdio.h>
#include<memory.h>
main(){
int s[105][1005]; //行为狗的数目，列为钱数
int price[105];
int cute[105];
int n,m;
while(~scanf("%d%d",&n,&m)){
memset(s, 0, sizeof(s));
for(int i=1; i<=n; i++){
scanf("%d%d", &price[i], &cute[i]);
}
for(int i=1; i<=m; i++){ //钱数从1~m
for(int j=1; j<=n ;j++){ //狗数从1~n
if(i>=price[j]){ //如果当前钱数大于狗的价钱，可买
int s1 = s[j-1][i]; //两种情况，不买，就直接等于之前的萌值
int s2 = s[j-1][i-price[j]]+cute[j]; //买，要把价钱减去当前狗的价钱，等于这个的价钱再加上萌值
s[j][i] = s1>s2?s1:s2;
}
else{ //不可买
s[j][i]=s[j-1][i];
}
}
}
printf("%d\n",s[n][m]);
}
}如果想要更清楚的话，我们可以把这个数组输出出来，这样更好理解一些：
简单的加个循环：
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
printf("%d ",s[i][j]);
}
printf("\n");
}
有点长（；´д｀）ゞ，也可以把这个数组翻转过来的，其实这个数组就是动态规划中我们需要理解的核心了。也就是按照规则一步一步走出来的。
end~
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/116834.html
