POJ 1384 Piggy-Bank

題意：
    存錢桶重量E，裝滿硬幣的時候重量為F，現在有N種硬幣，每種硬幣的價值為P重量為W，問這個存錢桶至少為多少錢？

想法：
    最小背包問題，先將dp[i]初始化成INF，將最大背包的max()改成min()就可以了。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	#define INF 999999999
	int dp[10005];
	int main()
	{
	int T, E, F;
	int N, P[501], W[501];
	scanf("%d", &T);
	while (T--) {
	// Input
	scanf("%d %d %d", &E, &F, &N);
	for (int i = 0; i < N; ++i)
	scanf("%d %d", &P[i], &W[i]);
	// Initial
	F = F-E;
	fill (dp, dp+10005, INF);
	dp[0] = 0;
	// Minimum Knapsack
	for (int i = 0; i < N; ++i)
	for (int j = 0; j+W[i] <= F; ++j)
	dp[j+W[i]] = min(dp[j+W[i]], dp[j] + P[i]);
	// Output
	if (dp[F] == INF) puts("This is impossible.");
	else printf("The minimum amount of money in the piggy-bank is %d.\n", dp[F]);
	}
	}

view raw [POJ] 1384 Piggy-Bank.cpp hosted with ❤ by GitHub