美美是学校的校花，所以呢为了保持身材，她决定每天的饮食不能超过C卡路里 (10 <= C <= 35,000)。但是你知道学校周边有太多太多的美食。她一般一天会吃B (1 <= B <= 21) 种食物（包括正餐和零食），每种食物的卡路里是已知的(范围：1~35,000)。美美没有自控能力，一旦她开始吃一种食物，她就一定会把这种食物吃完。美美当然想尽可能的多吃一点卡路里，但又不能违背自己定下的铁律。最槽糕的是，她对于数学完全不在行，只能拜托擅长编程的你咯。例如，它规定上限是40卡路里， 6种食物分别含有7, 13, 17, 19, 29, 31卡路里。美美可以吃7 + 31 = 38卡路里，但是可以获取得更多：7 + 13 + 19 = 39卡路里。没有更好的组合了。
输入共两行。 第一行，两个用空格分开的整数： C 和 B 第二行，B个用空格分开的整数，分别表示每种食物所含的卡路里。
输出共一行，一个整数，表示美美能获得的最大卡路里，使她不违背自己的原则。
样例输入40 6 7 13 17 19 29 31
样例输出39
这道题是常见的二维-动态规划题目，设解 f[b][c] ,描述当给定容量为 c , b 个物品价值时所能取得的最大值。令 value[b] 来存储b个物品各自的价值
那么对于 f[i][j] 第i个物品要么取要么不取，最大值就在这两种情况中产生，
所以递推公式为 f[i][j] = max ( f[i-1][j] , f[i-1][j-value[i]]+value[j] );
下面代码：
#include
int f[22][35001]={0};
int value[22];
int main()
{
int c,b,i,j;
scanf("%d%d",&c,&b);
for (i=1; i<=b; i++)
scanf("%d",&value[i]);
for (i=1; i<=b; i++)
{
for (j=1; j<=c; j++)
{
f[i][j] = f[i-1][j];
if (j>=value[i]&&f[i][j] 注意：
-
int f[22][35001]={0}; 定义在外部数据范围会更大
-
int value[22]; 作为全局变量初始化为0
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）