1、http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1406
2、题目：给定一定时间，已知吃一种汉堡用时为m分钟，吃另一种汉堡用时为n分钟，求在保证剩余时间最少的情况下，吃的汉堡的最大数，如果时间有剩余，那么也要输出剩余的时间
题目可以看成是简单的完全背包，不过相当于两次，第一次是在有限时间t内，能装的最大时间，第二次是在有限时间内且剩余时间最少的情况下，能装的最大个数，
3、题目：
| Problem C: | Homer Simpson |
Time Limit: 3 seconds Memory Limit: 32 MB |
|
| Homer Simpson, a very smart guy, likes eating Krusty-burgers. It takes Homer m minutes to eat a Krusty- burger. However, there?s a new type of burger in Apu?s Kwik-e-Mart. Homer likes those too. It takes him n minutes to eat one of these burgers. Given t minutes, you have to find out the maximum number of burgers Homer can eat without wasting any time. If he must waste time, he can have beer. |
Input
Input consists of several test cases. Each test case consists of three integers m, n, t (0 < m,n,t < 10000). Input is terminated by EOF.
Output
For each test case, print in a single line the maximum number of burgers Homer can eat without having beer. If homer must have beer, then also print the time he gets for drinking, separated by a single space. It is preferable that Homer drinks as little beer as possible.
Sample Input
3 5 54 3 5 55
Sample Output
18 17
Problem setter: Sadrul Habib Chowdhury
Solution author: Monirul Hasan (Tomal)
Time goes, you say? Ah no!
Alas, Time stays, we go.
#include<stdio.h>
#include<string.h>
#define N 10005
#include<algorithm>
using namespace std;
int dp[N];
int w[5];
int sum[N];
int main()
{int m,n,t;while(scanf("%d%d%d",&m,&n,&t)!=EOF){w[1]=m;w[2]=n;memset(sum,0,sizeof(sum));memset(dp,0,sizeof(dp));for(int i=1;i<=2;i++){for(int j=0;j<=t;j++){if(j>=w[i]){if(dp[j]<dp[j-w[i]]+w[i]){dp[j]=dp[j-w[i]]+w[i];sum[j]=sum[j-w[i]]+1;}else if(dp[j]==dp[j-w[i]]+w[i])//注意第一层的情况下，判断最优sum[j]=max(sum[j],sum[j-w[i]]+1);}}}if(dp[t]==t)printf("%d\n",sum[t]);elseprintf("%d %d\n",sum[t],t-dp[t]);}return 0;
}