当前位置：首页 > news >正文

HDU 2844 Coins

news 来源：原创 2024/5/2 21:23:50

像下面代码直接利用二进制求解多重背包会超时

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <vector>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 
 9 int main(){
10     int n,m;
11     while(cin>>n>>m && n && m){
12         vector<int> A(n),C(n);
13         for(int i = 0 ; i < n; i ++ ) cin >> A[i];
14         for(int i = 0 ; i < n; i ++ ) cin >> C[i];
15         vector<int> coin;
16 
17         for(int i = 0; i < n; i ++ ){
18             int tmp = 1;
19             while(C[i] > tmp){
20                 coin.push_back(tmp*A[i]);
21                 C[i] -= tmp;
22                 tmp <<=1;
23             }
24             coin.push_back(C[i]*A[i]);
25         }
26 
27         vector<int> dp(m+1,0);
28         for(int i = 0 ; i < coin.size(); i ++ ){
29             for(int j = m ; j >= coin[i]; j -- ){
30                 dp[j] = max(dp[j],dp[j-coin[i]] + coin[i]);
31             }
32         }
33 
34         int cnt = 0;
35         for(int i = 1; i <= m ; i++)
36             if(dp[i] != dp[i-1]) cnt++;
37         cout<<cnt<<endl;
38     }
39     return 0;
40 }

参考背包九讲，对多重背包进行优化

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <cstring>
 5 
 6 #define MAX 100000
 7 using namespace std;
 8 
 9 int dp[MAX];
10 
11 void CompletePack(int val, int m){
12     for(int j = val; j <= m; j ++ )
13         dp[j] = max(dp[j],dp[j - val]+ val);
14 }
15 
16 void ZeroOnePack(int val, int m){
17     for(int j = m; j >= val; j -- )
18         dp[j] = max(dp[j],dp[j - val]+ val);
19 }
20 
21 void MultiplePack(int val,int num, int m){
22     if(val*num >= m ){          //对于固定的m来说，相当于有无限个硬币，
23         CompletePack(val,m); //完全背包
24         return;
25     }
26     int k = 1;               //利用二进制优化转化为01背包
27     while( k < num){
28         ZeroOnePack(k*val,m);
29         num -= k;
30         k <<= 1;
31     }
32     ZeroOnePack(num*val,m);
33 }
34 
35 int main(){
36     int n,m;
37     while(cin>>n>>m && n && m){
38         vector<int> A(n),C(n);
39         for(int i = 0 ; i < n; i ++ ) cin >> A[i];
40         for(int i = 0 ; i < n; i ++ ) cin >> C[i];
41         //vector<int> dp(m+1,0);
42         memset(dp,0,sizeof(dp));
43         for(int i=0; i < n; i ++ )
44             MultiplePack(A[i],C[i],m);
45         int cnt = 0;
46         for(int i = 1; i <= m ; i++)
47             if(dp[i] == i) cnt++;
48         cout<<cnt<<endl;
49     }
50     return 0;
51 }