题目链接：

https://vjudge.net/contest/348156#problem/N

题面：

翻译：

在ACM可以做任何事情之前，必须准备好预算并获得必要的财政支持。这项行动的主要收入来自不可逆约束货币（IBM）。背后的想法很简单。每当某个ACM成员有零钱时，他就会把所有的硬币都扔进一个存钱罐。你知道这个过程是不可逆的，硬币不打碎猪就不能取出。在足够长的时间之后，储蓄罐里应该有足够的现金来支付所有需要支付的东西。
但是存钱罐有个大问题。无法确定里面有多少钱。所以我们可能会把猪打碎，结果发现钱不够。显然，我们想避免这种不愉快的局面。唯一的可能是称一下存钱罐的重量，试着猜里面有多少硬币。假设我们能够准确地确定猪的重量，并且我们知道某一货币的所有硬币的重量。然后我们可以保证存钱罐里有一些最低数额的钱。你的任务是找出最坏的情况，并确定存钱罐内的最低现金数额。我们需要你的帮助。再也没有过早破碎的猪了！

输入：
输入由T个测试用例组成。它们的数量（T）在输入文件的第一行给出。每个测试用例以包含两个整数E和F的行开始。它们表示空猪和装满硬币的猪的重量。两种重量均以克计。任何猪的体重都不会超过10公斤，即1<=E<=F<=10000。在每个测试用例的第二行，有一个整数N（1<=N<=500），它给出了在给定货币中使用的各种硬币的数量。接下来是N行，每行指定一种硬币类型。这些行各包含两个整数，Pand W（1<=P<=50000，1<=W<=10000）。P是硬币的货币单位，W是它的重量，单位为克。

输出：
为每个测试用例只打印一行输出。该行必须包含“存钱罐中的最小金额为X”这句话，其中X是使用给定总重量的硬币可以获得的最小金额。如果无法准确达到重量，请打印一行“这是不可能的”。

思路：

这道题目首先给出的硬币是类型，并且没有限制个数，所以就可以把它看为一个完全背包，而这个与常规的完全背包又不一样，我们解决的背包问题一般都是找到最大值，而这道题目我们需要找的是答道重量的最低金额，所以我们就要稍微转换一下思想，既然是要找到最小值，那我们把最初的dp数组里面的数值定义为一个大值，然后在单独把dp[0]定义为0，因为体积为0的时候你怎样都是0的钱，然后就可以通过min的函数来不断查找当前重量下最小钱的情况，然后就与常规的完全背包完全一样了

参考代码：

#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>#include<algorithm>using namespace std;int dp[10005];int v[10005];int w[10005];int main(){int t;scanf("%d",&t);while(t--){int e,f,n,a;scanf("%d%d",&e,&f);scanf("%d",&n);for(int i=0; i<n; i++){scanf("%d%d",&v[i],&w[i]);}a=f-e;for(int i=1; i<=a; i++){dp[i]=10000000;//把dp数组从1到a的每一位都定义为最大值，使得方便查找最小值}dp[0]=0;for(int i=0; i<n; i++){for(int j=w[i]; j<=a; j++){dp[j]=min(dp[j],dp[j-w[i]]+v[i]);//这个就是与常规的完全背包一点不同就是这个是查找最小值，常规的是查找最大值。。}}if(dp[a]<10000000)//如果dp小于定义时的最大值，就证明有情况可以把罐子装到正好重量{printf("The minimum amount of money in the piggy-bank is %d.\n",dp[a]);}else//如果没有，就证明没有一种情况可以把罐子正好装满{printf("This is impossible.\n");}}return 0;}