hdu 2844(二进制+多重背包)-白红宇

hdu 2844(二进制+多重背包)

阅读量：6707 次

发布时间：2019-06-25

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

题意：有一些货币告诉你每种的数量与币值。让你算在m内能组合成的的数值个数。

思路：数据量比较大，用多重背包的做法是会超时的，所以我们需要用二进制优化，记得以前听过这种写法，但是没有写过。今天终于做到这种题了第一次写参考了http://blog.csdn.net/hellobabygogo3/article/details/8013350 主要思路就是用二进制能组成所有v[i]以下的数。

代码如下：

1 /************************************************** 2  * Author     : xiaohao Z 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/ 4  * Last modified : 2014-04-02 22:58 5  * Filename     : hdu_2844.cpp 6  * Description     :  7  * ************************************************/ 8  9 #include 
      
       10 #include 
       
        11 #include 
        
         12 #include 
         
          13 #include 
          
           14 #include 
           
            15 #include 
            
             16 #include 
             
              17 #include 
              
               18 #include 
               
                19 #include 
                20 #define MP(a, b) make_pair(a, b)21 #define PB(a) push_back(a)22 23 using namespace std;24 typedef long long ll;25 typedef pair
                 
                   pii;26 typedef pair
                  
                    puu;27 typedef pair
                   
                     pid;28 typedef pair
                    
                      pli;29 typedef pair
                     
                       pil;30 31 const int INF = 0x3f3f3f3f;32 const double eps = 1E-6;33 const int LEN = 2001000;34 int dp[LEN];35 int n, m, a[LEN], c[LEN];36 37 int main()38 {39 // freopen("in.txt", "r", stdin);40 41 while(cin >> n >> m){42 if(!n && !m) break;43 memset(dp, 0, sizeof dp);44 for(int i=0; i
                      
                       > a[i];45 for(int i=0; i
                       
                        > c[i];46 dp[0] = 1;47 for(int i=0; i
                        
                         =j*a[i]; k--){51 if(dp[k - j*a[i]]) dp[k] = 1;52 }53 cnt -= j;54 }55 if(cnt){56 j = cnt;57 for(int k=m; k>=j*a[i]; k--) if(dp[k-j*a[i]])dp[k] = 1;58 }59 }60 int ans = 0;61 for(int i=1; i<=m; i++)if(dp[i]) ans ++;62 cout << ans << endl;63 }64 return 0;65 }

View Code

转载于:https://www.cnblogs.com/shu-xiaohao/p/3641986.html

你可能感兴趣的文章