经典完全背包问题。把幸福度看成价值,把卡路里看成重量,求卡路里刚好满足需求时的最大幸福度。

题目:飞机票直达(G - 湫湫系列故事——减肥记I


代码:

Memory: 2516 KB
Time: 46 MS
Language: C++
Result: Accepted
#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
using namespace std;
const int maxn=100+10;
const int maxm=200000;
int n, x[maxn], k[maxn], dp[maxm], m, i, j;
int main()
{
    while(~scanf("%d" ,&n)&&n)
    {
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)scanf("%d%d",&x[i],&k[i]);
        scanf("%d", &m);
        for(i=1;i<=n;i++)
            for(j=k[i];j<=m;j++)
                dp[j]=max(dp[j], dp[j-k[i]]+x[i]);
        printf("%d\n", dp[m]);
    }
    return 0;
}