高数Umaru系列（9）——哈士奇（01背包）

深藏阁楼爱情的钟 2022-07-12 04:17 111阅读 0赞

think:  
1 学会专心致志的做题，不要乱想太多，效率的降低往往因为分心和焦虑，学会平和的看待得失，不争一时之气。  
2 01背包同样离不开状态转移方程，动态规划的题目寻找合适的状态转移方程至关重要。  
3 时间复杂度和空间复杂度的理解和优化同样对于宏观学习的微观部分都有着不可忽视的重要作用。

[sdut原题链接][sdut]

高数Umaru系列（9）——哈士奇  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
由于高数巨养的喵星人太傲娇了，要天天吃新鲜猫粮而且还经常欺负高数巨，所以高数巨决定买几条哈士奇尝尝鲜。这天高数巨来到了二手狗市场买哈士奇，高数巨看完了所有的哈士奇，记下了每条哈士奇的价格，并根据对它们的好感程度给它们每只都赋予了一个萌值。高数现在手里有X元，她想通过购买若干条哈士奇来获得尽可能多的萌值。现在给定高数巨手里的钱X以及N条哈士奇的价格和萌值，求高数巨最多可获得多少萌值

Input  
多组输入。  
对于每组输入，第一行有两个整数N，X（1 < = N < = 100，1 < = X < = 1000），分别表示哈士奇的数量和高数巨的钱数  
接下来的N行每行有两个整数Pi，Mi（1 < = Pi,Mi < = 100），分别表示第i条哈士奇的价格和萌值

Output  
对于每组数据，输出一个整数，表示高数巨最多可以获得的萌值，每组输出占一行

Example Input  
2 100  
50 20  
60 40  
3 100  
20 55  
20 35  
90 95  
1 10  
20 50

Example Output  
40  
95  
0

Hint

Author  
Shannon

#include <stdio.h>
    #include <string.h>
    #define Max(a, b) (a > b? a: b)
    int main()
    {
        int a[140], b[140], dp[1400];
        int N, X, i, j;
        while(scanf("%d %d", &N, &X) != EOF)
        {
        
            memset(dp, 0, sizeof(dp));
            for(i = 0; i < N; i++)
            {
        
                scanf("%d %d", &a[i], &b[i]);
            }
            for(i = 0; i < N; i++)
            {
        
                for(j = X; j >= 0; j--)
                {
        
                    if(j >= a[i])
                    {
        
                        dp[j] = Max(dp[j], dp[j-a[i]] + b[i]);
                    }
                }
            }
            printf("%d\n", dp[X]);
        }
        return 0;
    }
    
    
    /***************************************************
    User name: jk160630
    Result: Accepted
    Take time: 0ms
    Take Memory: 108KB
    Submit time: 2017-02-10 11:02:24
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2007/pid/3358