poj 1384

完全背包

要点：要求的是最小为多少，，所以需要将f[] 初始化为最大。其他的于完全背包一样可以

 1 #include <iostream>
 2 #define maxn 5000000
 3 using namespace std;
 4 int fa[10005];
 5 int w[10005],v[10005];
 6 int main()
 7 {
 8     int t;
 9     cin>>t;
10     while(t--){
11         int e,f;
12         cin>>e>>f;
13         int ww = f-e;
14         int n;
15         cin>>n;
16         for(int i=1;i<=n;i++)
17             cin>>v[i]>>w[i];
18         for(int i=1;i<=ww;i++)
19             fa[i] = maxn;
20 
21         for(int i=1;i<=n;i++)
22         for(int j= w[i];j<=ww;j++){
23             if(fa[j]>fa[j-w[i]]+v[i])
24                 fa[j] = fa[j-w[i]]+v[i];
25         }
26         if(fa[ww]!=maxn)
27             cout<<"The minimum amount of money in the piggy-bank is "<<fa[f-e]<<"."<<endl;
28         else
29             cout<<"This is impossible."<<endl;
30     }
31     return 0;
32 }

直接带模版