【DP温习3—完全背包】HDU 1114——Piggy-Bank

【DP复习3—完全背包】HDU 1114——Piggy-Bank

题目：点击打开链接

完全背包，与0-1背包不同的是第二次遍历的顺序，倒过来就行，求最小值就改成MIN，其他的没什么变化。

另外要注意初始化的值。因为题目要求恰好装满，而且要求的值要尽量小，所以将dp[0]设为0，其余设为无穷大（如果没有要求恰好装满的话，全0）。

最后别忘了判断时减去初始给的值。

#include <iostream>
#include <cstring>
using namespace std;

const int INF=0x7FFFFFF;
int dp[100005];
int value[1000],weight[1000];

int min(int a,int b)
{
	if(a<=b)
		return a;
	else
		return b;
}

int main()
{
	int testcase;
	int needweight,totalmoney,pignum;
	cin>>testcase;
	while(testcase--)
	{
		memset(value,0,sizeof(value));
		memset(weight,0,sizeof(weight));
		for(int i=1;i<100005;i++)
		{
			dp[i]=INF;
		}
		dp[0]=0;


		cin>>needweight>>totalmoney;
		cin>>pignum;
		for(int i=0;i<pignum;i++)
		{
			cin>>weight[i]>>value[i];
		}
		
		totalmoney-=needweight;//减去初始的重量 
		
		for(int i=0;i<pignum;i++)
		{
			for(int j=value[i];j<=totalmoney;j++)
			{
				dp[j]=min(dp[j],dp[j-value[i]]+weight[i]);
			}
		}
			if(dp[totalmoney]!=INF)
			{
				cout<<"The minimum amount of money in the piggy-bank is "<<dp[totalmoney]<<"."<<endl;
			}
			else
				cout<<"This is impossible."<<endl;
		
		
	}
		
	return 0;
}