背包问题拓展

这篇博客主要讲解当背包装满时，使得背包总价值最小的方案。
这个问题主要涉及到两个问题。

1. 背包必须装满。
2. 总价值最小

以前的背包都是体积最大是多少时，总价值多大。并不一定要装满。
那，我们怎么解决呢？

我们让dp赋值为INF（最大值），dp[0]为0，这样每次状态转移时，都求最小值，我们就可以保证每次的转移都是由dp[0]转移过来，就可以确定是刚好体积为v的时候的最小价值。

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int t,E,F,n,p,w,dp[10010],v;
int main()
{
	cin>>t;
	while(t--)
	{
		memset(dp,inf,sizeof(dp));
		dp[0]=0;		
		cin>>E>>F;
		v=F-E;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>p>>w;
			for(int j=w;j<=v;j++)
			{
					dp[j]=min(dp[j],dp[j-w]+p);
			}
		}
		if(dp[v]==inf)	cout<<"This is impossible."<<endl;
		else cout<<"The minimum amount of money in the piggy-bank is "<<dp[v]<<'.'<<endl;
	}
	return 0;
}