【算法系列学习】[kuangbin带你飞]专题十二 基础DP1 F - Piggy-Bank 【完全背包问题】

时间:2022-09-04 02:59:24

https://vjudge.net/contest/68966#problem/F

http://blog.csdn.net/libin56842/article/details/9048173

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=1e4+;
int dp[maxn];
int weight[];
int money[];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
// memset(dp,0,sizeof(dp));
int E,F;
scanf("%d%d",&E,&F);
int v=F-E;
for(int i=;i<=v;i++)
{
dp[i]=INF;
}
dp[]=;
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&money[i],&weight[i]);
}
for(int i=;i<=n;i++)
{
for(int k=weight[i];k<=v;k++)
{
dp[k]=min(dp[k],dp[k-weight[i]]+money[i]);
}
}
if(dp[v]<INF)
{
printf("The minimum amount of money in the piggy-bank is %d.\n",dp[v]);
}
else
{
printf("This is impossible.\n");
} }
return ;
}