HDU 4508 湫湫系列故事——减肥记I （完全背包）

题意：有n种食物，每种食物可以给湫湫带来一个幸福感a，同时也会给她带来b的卡路里的摄入，然后规定她一天摄入的卡路里的量不能超过m，一共有n种食物，问可以得到的

最大的幸福感是多少？

解题报告：一开始以为是01背包，没看题，然后发现题目里面没有说每种食物只能吃一次，才发现是个完全背包，一开始还以为题目的第二组测试数据是错的，无语。。。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int a[105],b[105],ans[100005];

int main()
{
    int n,m;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i = 0;i < n;++i)
        scanf("%d%d",&a[i],&b[i]);
        scanf("%d",&m);
        memset(ans,0,sizeof(ans));
        for(int i = 0;i < n;++i)
        for(int k = 1;k <= m / b[i];++k)
        for(int j = m;j >= k * b[i];--j)
        ans[j] = max(ans[j],ans[j-k * b[i]] + k * a[i]);
        int Mtot = ans[0];
        for(int i = 0;i <= m;++i)
        Mtot = max(ans[i],Mtot);
        printf("%d
",Mtot);
    }
    return 0;
}