POJ 1276 Cash Machine

題意：
    不同價值Dk元的鈔票有Nk張，現在要求用這些鈔票能湊出最接近cash是多少元？

想法：
    背包問題，dp[i]=k表示i重量上限的背包最多能裝k價值的東西，題目給的Nk表示該物品的數量，而Dk是重量同時也是價值，這樣去求背包問題。因為這題時間限制，須採用和POJ 1024一樣的做法，將Nk件捆成1+2+4+8+16+32+....+left的形式，減低運算次數。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int dp[100005];
	int main()
	{
	int cash, N, n[11], D[11];
	while (scanf("%d %d", &cash, &N) != EOF) {
	// Input
	for (int i = 0; i < N; ++i)
	scanf("%d %d", &n[i], &D[i]);
	// Initial
	fill(dp, dp+cash+1, 0);
	// Knapsack
	for (int i = 0; i < N; ++i) {
	int left = n[i];
	while (left > 10) {
	for (int j = 1; j <= left; left -= j, j *= 2)
	for (int k = cash; k - D[i]*j >= 0; --k)
	dp[k] = max(dp[k], dp[k-D[i]*j] + D[i]*j);
	}
	for (int j = 0; j < left; ++j)
	for (int k = cash; k - D[i] >= 0; --k)
	dp[k] = max(dp[k], dp[k-D[i]] + D[i]);
	}
	printf("%d\n", dp[cash]);
	}
	}

view raw [POJ] 1276 Cash Machine.cpp hosted with ❤ by GitHub