uva 10465 Homer Simpson(完全背包）
题目连接：10465 - Homer Simpson
题目大意：有两种汉堡包， 给出吃汉堡的时间， 再给出总的时间， 尽量不浪费给出的时间，输出能最多吃的汉堡个数， 如果一定需要浪费时间， 输出浪费时间最少的时刻内能吃的最多汉堡个数， 并再后面输出浪费掉的时间。
解题思路：因为汉堡可以无限制的使用， 所以相当于是完全背包问题，dp[i]就是代表在i分钟之内最多能吃多少汉堡（时间完全使用完）， dp[i] = 0说明该时间是有浪费的。
#include <stdio.h>#include <string.h>const int N = 10005;int a, b, sum, dp[N * 2];void solve() { memset(dp, 0, sizeof(dp)); dp[a] = 1; for (int i = 0; i < N; i++) if (dp[i] && dp[i] + 1 > dp[i + a]) dp[i + a] = dp[i] + 1; dp[b] = 1; for (int i = 0; i < N; i++)if(dp[i] && dp[i] + 1 > dp[i + b]) dp[i + b] = dp[i] + 1;}int main() { while (scanf("%d%d%d", &a, &b, &sum) == 3) {int flag = 1;solve();for (int i = 0; i <= sum; i++) if (dp[sum - i]) {printf("%d", dp[sum - i]);if (i) printf(" %d", i);printf("\n");flag = 0;break; }if (flag) printf("0 %d\n", sum); } return 0;}