UVa:10465 Homer Simpson

완전 가방+욕심.
1Y.
완전 배낭의 사고방식을 이용하여 햄버거를 먹는 데 필요한 최대 시간을 구하다.그리고 구조가 가장 잘 될 때 매번 적은 햄버거를 먼저 고려하면 햄버거를 최대한 많이 먹을 수 있다.
 
 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int dp[3][10005];
int main()
{
    int m,n,t;
    while(scanf("%d%d%d",&m,&n,&t)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        int v[3],ans=0;
        v[1]=max(m,n),v[2]=min(m,n);
        for(int i=1; i<=2; ++i)
            for(int j=0; j<=t; ++j)
                if(j>=v[i])
                    dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+v[i]);
                else dp[i][j]=dp[i-1][j];
        int ii=2,jj=t;
        while(ii>0&&jj>0)
        {
            if(dp[ii][jj]==dp[ii][jj-v[ii]]+v[ii])
            {
                ans++;
                jj=jj-v[ii];
            }
            else  ii--;
        }
        printf("%d",ans);
        if(t-dp[2][t])
            printf(" %d",t-dp[2][t]);
        printf("
");
    }
    return 0;
}