标签归档:完全背包

HDU – 1114 Piggy-Bank (完全背包)

HDU 1114

应该是完全背包裸题吧,第一次练习...

与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;
}