其实这道题在寒假自学训练赛的时候就做过,不过感觉现在的理解跟当时真的不一样,大一半年过去了,变了这么多,我们都在进步,一回头便走出了这么远...
好了,题目很简单,一个背包,装不满做一个标记就行了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <algorithm>
using namespace std;
long long dp[];
int money[], weight[];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int w1,w2;
scanf("%d%d",&w1,&w2);
int all = w2 - w1;
dp[] = ;
for(int i = ;i <= all;i++)
dp[i] = ;
int kind;
scanf("%d",&kind);
for(int i = ;i < kind;i++)
{
scanf("%d%d",&money[i],&weight[i]);
}
for(int i = ;i < kind;i++)
{
for(int j = weight[i]; j <= all;j++)
{
dp[j] = min(dp[j],dp[j-weight[i]] + money[i]);
}
}
if(dp[all] == )
printf("This is impossible.\n");
else printf("The minimum amount of money in the piggy-bank is %lld.\n",dp[all]);
}
return ;
}