UVA 10465 Homer Simpson(dp + 完全双肩包)
UVA 10465 Homer Simpson(dp + 完全背包)
| 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
题意：有两种汉堡一种吃一个要n分钟，一种要m分钟，现在给定t分钟。要求尽量不浪费时间去吃汉堡，求出吃汉堡的个数，如果一定要浪费时间，那么还要输出浪费掉的时间。
思路：完全背包，等于是给定两个物品，时间代表容量，价值都为1，求出dp[t]的最大值。
代码：
#include <stdio.h>
#include <string.h>
int m, n, t, dp[10005], i;
int max(int a, int b) {
return a > b ? a : b;
}
int main() {
while (~scanf("%d%d%d", &m, &n, &t)) {
memset(dp, -1, sizeof(dp));
dp[0] = 0;
for (i = m; i <= t; i ++) {
if (dp[i - m] != - 1)
dp[i] = max(dp[i - m] + 1, dp[i]);
}
for (i = n; i <= t; i ++) {
if (dp[i - n] != -1)
dp[i] = max(dp[i - n] + 1, dp[i]);
}
if (dp[t] != -1)
printf("%d", dp[t]);
else {
for (i = t; i >= 0; i --)
if (dp[i] != -1) {
printf("%d %d", dp[i], t - i);
break;
}
}
printf("\n");
}
return 0;
}