HDOJ(HDU).4508 湫湫系列故事――减肥记I (DP 完全背包)

题意分析

裸完全背包

代码总览

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define nmax 100005

#define nn 105

using namespace std;

int dp[nmax];

struct item{

    int hap;

    int kal;

    double rate;

}a[nmax];

bool cmp(item a,item b)

{

    return a.rate>b.rate;

}

int main()

{

    //freopen("in.txt","r",stdin);

    int n;

    while(scanf("%d",&n) != EOF){

        memset(dp,0,sizeof(dp));

        for(int i = 1; i<=n; ++i) {scanf("%d%d",&a[i].hap,&a[i].kal); a[i].rate = a[i].hap/a[i].kal;}

        sort(a+1,a+1+n,cmp);

        int m;

        scanf("%d",&m);

        for(int i =1; i<=n; ++i){

            for(int j =a[i].kal;j<=m;++j){

                dp[j] = max(dp[j],dp[j-a[i].kal]+a[i].hap);

            }

        }

        printf("%d\n",dp[m]);

    }

    return 0;

}