校花美美（C语言代码解析）

题目描述

美美是学校的校花，所以呢为了保持身材，她决定每天的饮食不能超过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]

注意：

1. int f[22][35001]={0};        定义在外部数据范围会更大

2. int value[22];                   作为全局变量初始化为0

 

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/langs/793073.html