uva10465 - Homer Simpson（完全背包）

uva10465 - Homer Simpson（完全背包）

題目：10465 - Homer Simpson（完全背包）

題目大意：有個家伙很喜歡吃burger，現在有兩種burger，然後給出吃這兩種burger的時間，然後問你在指定的時間內，他能吃最多的burger的個數是多少。如果不能夠用完的話，那麼剩余時間就拿來喝水，要求喝水的時間盡量短。

解題思路：完全背包。狀態轉移方程：dp【t】在t時間內能吃的最多的burger數目。dp【t + v【i】】 = max （dp【t + v【i】】，dp【t】 + 1）.

代碼：

#include 
#include 

const int N = 2;
const int maxn = 10000;

int dp[maxn];
int v[N];
int t;

int Max (const int a, const int b) { return a > b? a: b; }

int main () {
	
	while (scanf ("%d%d%d", &v[0], &v[1], &t) != EOF) {

		memset (dp, -1, sizeof (dp));
		dp[0] = 0;
		for (int i = 0; i <= N - 1; i++) {
			for (int j = 0; j <= t - v[i]; j++) {
			
				if (dp[j] != -1)
					dp[j + v[i]] = Max (dp[j + v[i]], dp[j] + 1);			
			}
		}

		int i;
		for (i = t; i >= 0; i--)
			if (dp[i] != -1)
				break;
		printf ("%d", dp[i]);

		if (i != t)
			printf (" %d\n", t - i);
		else
			printf ("\n");
	}
	return 0;
}