Lightoj 1127 - Funny Knapsack 【二分】-白红宇

Lightoj 1127 - Funny Knapsack 【二分】

阅读量：7026 次

发布时间：2019-06-28

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

题目链接：

题意：有n个物体（n<30）和一个容量为W的容器。问将容器不装满的放置物品的方式有多少种。

思路：状态压缩+二分。将前n/2个物体看做一个总体，将剩下的看做一个总体。1<<(n/2)个状态代表前一半的物品使用情况，然后求出每一种状态的总的体积。排序。对于后面的那一半也是。答案仅仅需枚举一半然后在还有一半中找和W差的下界就可以。

代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         #include 
                         
                          #include 
                          
                           #include 
                           
                            #include 
                            
                             #include 
                             
                              #include 
                              
                               #include 
                               
                                #include 
                                
                                 #include 
                                 
                                  using namespace std;int n;long long w;long long a[1000000];long long s1[1000000];long long s2[1000000];int main(){ int t; scanf("%d", &t); int cases = 1; while (t--) { memset(s1, 0, sizeof(s1)); memset(s2, 0, sizeof(s2)); memset(a, 0, sizeof(a)); scanf("%d %lld", &n, &w); for (int i = 0; i < n; i++) scanf("%lld", &a[i]); int t1 = n >> 1; int t2 = n - t1; int r1 = 1 << t1; int r2 = 1 << t2; for (int i = 0; i < r1; i++) for (int j = 0; j < t1; j++) { if (i &(1 << j)) s1[i] += a[j]; } for (int i = 0; i < r2; i++) for (int j = 0; j < t2; j++) { if (i &(1 << j)) s2[i] += a[t1 + j]; } sort(s2, s2 + r2 ); long long ans = 0; for (int i = 0; i < r1; i++) { if (w - s1[i] >= 0) ans += upper_bound(s2, s2 + r2, w - s1[i]) - s2; } printf("Case %d: %lld\n", cases++, ans); } return 0;}

转载地址：http://ptoxl.baihongyu.com/

你可能感兴趣的文章