hdoj 3732 Ahui Writes Word (多重背包)

      之前在做背包的题目时看到了这道题，一看，大喜，这不是裸裸的01背包吗！！  然后华丽丽的超时，相信很多人也和我一样没有考虑到数据量的大小。

      时隔多日，回过头来看这道题，依旧毫无头绪。。。。不过相比之前，我看到了更多细节。

      来看题目吧，可能有100000个单词，然后只有1000ms，但看包的大小，有10000，这样只能允许nlog(n)的算法，还有，每个单词的价值和花费都很小（不大于十），如果不考虑单词的不同，只考虑价值和花费只有最多100种东西，但如果把这些按多重背包的方法来计算依旧会超时，很容易想到和之前01背包的时间复杂度是一样的。

      还记得多重背包可以转换为01背包吗？？我们不妨把这些物品进行打包，把每种物品分别1个、2个、4个…………（2^k）个进行打包，如果不足2^k个则单独打包，然后把每一包看做一件物品，继续使用01背包的方法进行计算，这样我们就把原来O(nc)的时间复杂度降到了O(clogn)。

  

   

    

     

    
    

     

      //hdoj 3732
     
    
   

    

     

    
    

     

      //2013-08-10-16.53
     
    
   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <string.h>
     
    
   

    

     

    
    

     

      #include <algorithm>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int dp[10005];
     
    
   

    

     

    
    

     

      int vc[11][11];
     
    
   

    

     

    
    

     

      int w[10005];
     
    
   

    

     

    
    

     

      int v[10005];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int n, c;
     
    
   

    

     

    
    

     
    char s[100];
     
    
   

    

     

    
    

     
    while (scanf("%d %d", &n, &c) != EOF)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        int a, b;
     
    
   

    

     

    
    

     
        memset(dp, 0, sizeof(dp));
     
    
   

    

     

    
    

     
        memset(vc, 0 ,sizeof(vc));
     
    
   

    

     

    
    

     
        for (int i = 1; i <= n; i++)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     
            scanf("%s %d %d", &s, &a, &b);
     
    
   

    

     

    
    

     

                  vc[a][b]++;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        int cnt = 1;
     
    
   

    

     

    
    

     
        for (int i = 1; i <= 10; i++)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     
            for (int j = 1; j <= 10; j++)
     
    
   

    

     

    
    

     

                  {
     
    
   

    

     

    
    

     
                if (vc[i][j])
     
    
   

    

     

    
    

     

                      {
     
    
   

    

     

    
    

     
                    int tmp = 1;
     
    
   

    

     

    
    

     
                    while (vc[i][j] > tmp)
     
    
   

    

     

    
    

     

                          {
     
    
   

    

     

    
    

     

                              w[cnt] = tmp*j;
     
    
   

    

     

    
    

     

                              v[cnt] = tmp*i;
     
    
   

    

     

    
    

     

                              vc[i][j] -= tmp;
     
    
   

    

     

    
    

     

                              cnt++;
     
    
   

    

     

    
    

     

                              tmp <<= 1;
     
    
   

    

     

    
    

     

                          }
     
    
   

    

     

    
    

     

                          w[cnt] = j*vc[i][j];
     
    
   

    

     

    
    

     

                          v[cnt] = i*vc[i][j];
     
    
   

    

     

    
    

     

                          cnt++;
     
    
   

    

     

    
    

     

                      }
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        for (int i = 1; i < cnt; i++)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     
            for (int j = c; j >= w[i]; j--)
     
    
   

    

     

    
    

     

                      dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        printf("%d\n", dp[c]);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。

原文链接：xindoo.blog.csdn.net/article/details/9933741