UVa 10465 Homer Simpson

題意：
    有兩種漢堡A和B，吃一個A需要m分鐘，吃一個B需要n分鐘。現在給你t分鐘，問在"剛好用完"t分鐘的情況下最多能吃幾個漢堡k，輸出k；如果沒辦法剛好用完t分鐘，則找最接近t分鐘的k値，輸出k和差幾分鐘。

想法：
    背包問題，重量和物品價值都是時間，Time[i]=k表示給你i分鐘最多能用到k分鐘，如果Time[t]==t表示剛好用完t分鐘，否則最多就是用到Time[t]分鐘，差t-Time[t]分鐘；另外用num[i]=k用來記錄i分鐘能吃k個漢堡。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int Time[10005];
	int num[10005];
	int Knapsack(int m, int t)
	{
	for (int i = 0; i + m <= t; ++i)
	if (Time[i+m] < Time[i] + m) {
	Time[i+m] = Time[i] + m;
	num[i+m] = num[i] + 1;
	}
	}
	int main()
	{
	int m, n, t;
	while (scanf("%d %d %d", &m, &n, &t) != EOF) {
	fill(Time, Time+t+1, 0);
	fill(num, num+t+1, 0);
	if (m > n) swap(m, n);
	Knapsack(m, t);
	Knapsack(n, t);
	if (Time[t] == t) printf("%d\n", num[t]);
	else printf("%d %d\n", num[Time[t]], t-Time[t]);
	}
	}

view raw [UVa] 10465 Homer Simpson.cpp hosted with ❤ by GitHub