POJ 1742 Coins（多重背包，优化）-白红宇

POJ 1742 Coins（多重背包，优化）

阅读量：7077 次

发布时间：2019-06-28

本文共 3559 字，大约阅读时间需要 11 分钟。

《挑战程序设计竞赛》上DP的一道习题。

很裸的多重背包。下面对比一下方法，倍增，优化定义，单调队列。

一开始我写的倍增，把C[i]分解成小于C[i]的2^x和一个余数r。

dp[i][j]的定义前i个数字能否到凑出j来，改成一位滚动数组。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 //#include
                 
                  using namespace std;#define PS push#define PB push_back#define MP make_pair#define fi first#define se secondconst int maxm = 1e5+5;const int maxn = 101;bool dp[maxm];int A[maxn], C[maxn];int n, m;inline int read(){ int ret; char c; while(c = getchar(),c<'0'||c>'9'); ret = c-'0'; while(c = getchar(),c>='0'&&c<='9') ret = ret*10 + c-'0'; return ret;}//#define LOCALint main(){#ifdef LOCAL freopen("in.txt","r",stdin);#endif dp[0] = true; while(scanf("%d%d",&n,&m),n+m){ for(int i = 0; i < n; i++) A[i] = read(); for(int i = 0; i < n; i++){ C[i] = read(); } memset(dp+1,0,sizeof(bool)*m); for(int i = 0; i < n; i++){ int b = 1,vol = A[i]; while((1<
                  
                   <=C[i]+1){ //11...111 (b) <= C[i] -> 100.... <= C[i]+1 for(int S = m; S >= vol; S--){ dp[S] = dp[S-vol]||dp[S]; } b++; vol<<=1; } int r = C[i]-(1<<(b-1))+1; if(r){ int Vol = A[i]*r; for(int S = m; S >= Vol; S--){ dp[S] = dp[S-Vol]||dp[S]; } } } int ans = 0; for(int i = 1; i <= m; i++) ans += dp[i]; printf("%d\n",ans); } return 0;}

binary

复杂度是O(n*m*sigma(logC[i]))。然后果断就TLE了。

再优化只有单调队列了，扎扎并没有想到怎么用单调队列。

书上的解法是优化定义，同样的时间复杂度记录bool信息太浪费了。

dp[i][j]表示前i种凑出面值j时第i种硬币最多的剩余。

核心代码：

int ans = 0;        memset(dp+1,-1,sizeof(int)*m);        for(int i = 0; i < n; i++){            for(int j = 0; j <= m; j++){                if(~dp[j]) dp[j] = C[i]; //之前凑出了j                else if(j >= A[i] && dp[j-A[i]]>0) { //还可以在凑                    dp[j] = dp[j-A[i]] - 1;                    ans++;                }else dp[j] = -1; //凑不出            }        }

跑了1985ms。

另外还发现一件有意思的事情，

当我用一个临时变量数组cnt[j]记录凑出j的最小次数的时候，跑了1235ms。（系统分配似乎更快一点？

int ans = 0;        memset(dp+1,0,sizeof(bool)*m);        for(int i = 0; i < n; i++){            int cnt[maxm] = {};            for(int j = A[i]; j <= m; j++){                if(!dp[j] && dp[j-A[i]] && cnt[j-A[i]] < C[i]){                    cnt[j] = cnt[j-A[i]] + 1;                    ans++;                    dp[j] = true;                }            }        }

参考了之后，明白了单调队列的做法的。

总体来说是划分同余类，对于一个同余类用单调队列维护滑动窗口的最小值。（左端为最多减去C[i]个物品的的状态

这道题只要判断存在性，连单调性都用不上(insert不需要删除队尾元素)，只要维护滑动窗口的和以及大小就可以了。

但是这道题数据丧心病狂，直接分组常数比较大TLE了。我改成判断0-1和完全才2891 ms飘过（常数写丑了

int ans = 0;        memset(dp+1,0,sizeof(bool)*m);        for(int i = 0; i < n; i++){            if(C[i] == 1){                for(int j = m; j >= A[i]; j--){                    dp[j] = dp[j-A[i]] || dp[j];                }            }            else if(A[i]*C[i] >= m){                for(int j = A[i]; j <= m; j++){                    dp[j] = dp[j-A[i]] || dp[j];                }            }            else {                for(int r = 0; r < A[i]; r++){                    int sum = 0, hd = 0, rr = 0;                    for(int j = r; j <= m; j += A[i]){                        if(rr - hd > C[i]){                            sum -= q[hd++];                        }                        sum += q[rr++] = dp[j];                        if(sum) dp[j] = true;                    }                }            }        }        for(int i = 1; i <= m; i++) ans += dp[i];

似乎完全的情况比较多的情况，我只改了一个语句的不同结果。。

dp[j] = dp[j-A[i]] || dp[j]; 2891 ms

if(dp[j-A[i]]) dp[j] = true; 2813 ms

if(dp[j-A[i]] && !dp[j]) dp[j] = true; 2110 ms

转载于:https://www.cnblogs.com/jerryRey/p/4883582.html

你可能感兴趣的文章