HDU 1114 PiggyBank

利用传统的完全背包解法会超时，下面代码超时

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 
 5 #define INF 1<<30
 6 using namespace std;
 7 
 8 int main(){
 9     int T;
10     cin >> T;
11     while(T--){
12         int E,F;
13         cin >>E>>F;
14         int pigWeight =F-E;
15         int n;
16         cin >> n;
17         vector<int> p(n),w(n);
18         for(int i = 0; i < n; i ++ ){
19             cin >> p[i]>>w[i];
20         }
21         vector<int> dp(pigWeight+1,INF);
22         dp[0]=0;
23         for(int i = 0; i < n; i ++ ){
24             for(int j = w[i]; j <= pigWeight; j ++){
25                 for(int k =0; k <= j/w[i]; k ++){
26                     dp[j] = min(dp[j],dp[j-w[i]]+p[i]);
27                 }
28             }
29         }
30         if(dp[pigWeight] == INF) cout<<"This is impossible."<<endl;
31         else cout<<"The minimum amount of money in the piggy-bank is "<<dp[pigWeight]<<"."<<endl;
32 
33     }
34 
35     return 0;
36 }

需要对完全背包进行优化，具体参考背包九讲和 http://blog.csdn.net/wumuzi520/article/details/7014830

优化后代码

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 
 5 #define INF 1<<30
 6 using namespace std;
 7 
 8 int main(){
 9     int T;
10     cin >> T;
11     while(T--){
12         int E,F;
13         cin >>E>>F;
14         int pigWeight =F-E;
15         int n;
16         cin >> n;
17         vector<int> p(n),w(n);
18         for(int i = 0; i < n; i ++ ){
19             cin >> p[i]>>w[i];
20         }
21         vector<int> dp(pigWeight+1,INF);
22         dp[0]=0;
23         for(int i = 0; i < n; i ++ ){
24             for(int j = w[i]; j <= pigWeight; j ++){
25                 dp[j] = min(dp[j],dp[j-w[i]]+p[i]);
26             }
27         }
28         if(dp[pigWeight] == INF) cout<<"This is impossible."<<endl;
29         else cout<<"The minimum amount of money in the piggy-bank is "<<dp[pigWeight]<<"."<<endl;
30     }
31 
32     return 0;
33 }