HDU 1114 完全背包

HDU 1114 完全背包

题意

给你一个空的存钱罐的重量，和一个装了一些钱后的存钱罐的重量，然后给你n个硬币的价值p和重量w，保证存钱罐中的硬币的种类都在这n种硬币中。现在让我们求在给定重量的情况下，存钱罐内硬币的金额最少是多少。

解题思路

因为每一种硬币的使用数目没有限制，所以我们可以使用完全背包来进行解决。

我们定义dp[i][j]的含义为在仅可以使用前i种硬币，并且正好装满背包容量为j的前提下，硬币的最小金额。

这里我们需要初始化一些初始值，dp[i][0] = 0这个状态表示在背包容量为0的前提下，无论使用前多少种硬币，我们都不能放硬币，因而总的金额为0。其他的状态dp[i][j] = inf，因为这里的值我们还不知道，并且我们要求最小值，所以我们给不知道的状态赋值一个很大的数，这样在进行状态递推的时候就可以使用min()这个函数来进行了。

代码实现

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<sstream>
typedef long long ll;
using namespace std;
const double esp=1e-6;
const int inf=0x3f3f3f3f;
const int MAXN=500+7;
const int MAXV=1e4+7;
int w[MAXN], val[MAXN];
int dp[MAXV]; 
int e, f, n, t;
int main()
{
	cin>>t; 
	while(t--){
		cin>>e>>f;
		int V = f - e;
		cin>>n;
		for(int i=1; i<=n; i++)
			cin>>val[i]>>w[i];
		for(int i=0; i<=V; i++)
			dp[i] = inf;
		dp[0] = 0;
		for(int i=1; i<=n; i++)
			for(int j=w[i]; j<=V; j++)
				dp[j] = min(dp[j], dp[j-w[i]] + val[i]);
		if(dp[V] < inf)
			cout<<"The minimum amount of money in the piggy-bank is "<<dp[V]<<".
";
		else cout<<"This is impossible.
";
	}
	return 0;
}