差不多是一个裸的完全背包,只是要求满容量的最小值而已。那么dp值全部初始化为inf,并且初始化一下dp[0]即可。代码如下:
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = + ;
const int W = + ;
const int inf = 0x3f3f3f3f; int dp[W];
int val[N],w[N]; int main()
{
int T; scanf("%d",&T);
while(T--)
{
int E, F;
scanf("%d%d",&E,&F);
F -= E;
int n;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d%d",val+i,w+i);
memset(dp,inf,sizeof dp);
dp[] = ;
for(int i=;i<=n;i++)
{
for(int j=w[i];j<=F;j++)
{
dp[j] = min(dp[j], dp[j-w[i]] + val[i]);
}
}
if(dp[F] == inf) puts("This is impossible.");
else printf("The minimum amount of money in the piggy-bank is %d.\n",dp[F]);
}
return ;
}