应该是完全背包裸题吧,第一次练习…
与01背包不同的是,j的正序循环保证了在同一个阶段之间的状态转移,即同一个物品可以使用多次.
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define maxn 0x3f3f3f3f
#define ll long long
using namespace std;
int n;
int w[505];
int v[505];
ll f[10005];
int main() {
int T;
cin>>T;
while (T--) {
for(int i=0;i<10005;++i){
f[i]=maxn;
}
int E,F;
scanf("%d%d",&E,&F);
int W=F-E;
scanf("%d",&n);
for(int i=0;i<n;++i){
scanf("%d%d",&v[i],&w[i]);
}
f[0]=0;
for(int i=0;i<n;++i){
for(int j=w[i];j<=W;++j){
f[j]=min(f[j],f[j-w[i]]+v[i]);
}
}
if(f[W]==maxn){
printf("This is impossible.\n");
}
else{
printf("The minimum amount of money in the piggy-bank is %lld.\n",f[W]);
}
}
return 0;
}