唔。。近期在练基础dp

这道题挺简单的（haha）。可是我仅仅想说这里得注意一个细节。

首先题意：

有T组例子，然后给出储蓄罐的起始重量E，结束重量F（也就是当它里面存满了零钱的时候）。然后给你一个数N，代表如今有N种类型的硬币。

然后接下来N行，每行分别有两个数字P,W，P代表的是这样的类型零钱的价值，W则代表的是这样的类型零钱的重量，零钱的数量不限。

然后要你输出在满足当前重量就是F的情况下（也就是重量刚好为F），输出所需零钱价值最少的情况。

思路：

非常显然，这明显就是一个全然背包。可是这里唯一要注意的地方就是在初始化的时候，由于我们要全然填满储蓄罐。所以初始化dp[0]=0； 然后又由于我们要求的是所需零钱价值最少的情况。所以其余的都得初始化为正无穷。

除了以上的情况。我相信其余的都不难了。

当dp[V]==inf 时。就说明此时是无解的。

#include<stdio.h>

#include<string.h>

#include<iostream>

#include<algorithm>

#include<set>

#include<map>

#include<math.h>

using namespace std;

#define maxn 10010

#define inf 99999999

int dp[maxn];

int v[555],w[555];

int main(){

	int T;

	scanf("%d",&T);

	while(T--){

		int e,f;

		scanf("%d%d",&e,&f);

		int V=f-e;

		int n;

		scanf("%d",&n);

		for(int i=1;i<=n;i++){

			scanf("%d%d",&v[i],&w[i]);

		}

		fill(dp,dp+maxn+1,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]]+v[i]);

			}

		}

		if(dp[V]==inf) printf("This is impossible.\n");

		else printf("The minimum amount of money in the piggy-bank is %d.\n",dp[V]);

	}

}

/*

3

10 110

2

1 1

30 50

*/