uva 10465 Homer Simpson(完全双肩包）

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;
}