P1441 砝码称重【搜索+01背包】

题目描述

现有n个砝码，重量分别为 $a_iai，在去掉 mm 个砝码后，问最多能称量出多少不同的重量（不包括 00）。$

请注意，砝码只能放在其中一边。

输入格式

第

第 $a_1, a_2, a_3,\ldots , a_na1,a2,a3,…,an，表示每个砝码的重量。$

输出格式

仅包括

输入输出样例

输入 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

3 1
1 2 2

输出 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

思路

　　搜索出抛弃个数为m的所有组合，在dfs的过程中给不用的砝码打上标记，然后利用01背包的方式求解最大的不同数字的组合即可。

　　这题不加优化，稳妥一点从5000种枚举到0，跑了将近700ms，如果随时记录可用砝码重量的最大值来优化这个过程，就像题解中那样，只要跑100ms左右。

CODE

   #include    <   bits/stdc++.h   >  
   #define    dbg(   x   ) cout    <<    #x    <<    "   =   "    << x    << endl  
   #define    eps    1   e   -   8  
   #define    pi    acos(   -   1.0   )  

   using    namespace std   ;  
   typedef    long    long LL   ;  

   const    int inf    =    0x   3f3f3f3f   ;  

   template   <   class T   >   inline    void    read(T    &   res   )  
   {  
          char c   ;T flag   =   1   ;  
          while((c   =   getchar())   <   '   0   '   ||c   >   '   9   '   )if(c   ==   '   -   '   )flag   =-   1   ;res   =c   -   '   0   '   ;  
          while((c   =   getchar())   >=   '   0   '   &&c   <=   '   9   '   )res   =res   *   10   +c   -   '   0   '   ;res   *=flag   ;  
   }  

   namespace _buff    {  
          const    size_t BUFF    =    1    <<    19   ;  
          char    ibuf   [BUFF   ],    *ib    = ibuf   ,    *ie    = ibuf   ;  
          char    getc()    {  
              if    (ib    == ie   )    {  
               ib    = ibuf   ;  
               ie    = ibuf    +    fread(ibuf   ,    1   , BUFF   , stdin   );  
              }  
              return ib    == ie    ?    -   1    :    *ib   ++   ;  
          }  
   }  

   int    qread()    {  
          using    namespace _buff   ;  
          int ret    =    0   ;  
          bool pos    =    true   ;  
          char c    =    getc();  
          for    (;    (c    <    '   0   '    || c    >    '   9   '   )    && c    !=    '   -   '   ; c    =    getc())    {  
              assert(   ~c   );  
          }  
          if    (c    ==    '   -   '   )    {  
           pos    =    false   ;  
           c    =    getc();  
          }  
          for    (; c    >=    '   0   '    && c    <=    '   9   '   ; c    =    getc())    {  
           ret    =    (ret    <<    3   )    +    (ret    <<    1   )    +    (c    ^    48   );  
          }  
          return pos    ? ret    :    -ret   ;  
   }  

   int n   , m   ;  
   int    a   [   50   ];  
   bool    vis   [   50   ];  
   int    f   [   50   ];  
   int maxx    =    0   ;  
   int maxn    =    0   ;  

   int    check()    {  
          int num    =    0   ,    f   [   20007   ]    =    {   0   };  
          f   [   0   ]    =    1   ;  
          for    (    int i    =    1   ; i    <= n   ;    ++i    )    {  
              if(   vis   [i   ])  
                  continue;  
              for    (    int j    = maxx   ; j    >=    0   ;    --j    )    {  
                  if(   f   [j   ])    {  
                      f   [j    +    a   [i   ]]    =    1   ;  
                  }  
              }  
          }  
          for    (    int i    =    1   ; i    <= maxx   ;    ++i    )    {  
              if(   f   [i   ])    {  
                  ++num   ;  
              }  
          }  
          return num   ;  
   }  

   void    dfs(   int    id   ,    int    sum   )    {  
          if(check()    <= maxn   )    {  
              return;  
          }  
          if(sum    == m    +    1   )    {  
              int k    =    check();  
           maxn    =    max(maxn   , k   );  
              return;  
          }  
          for    (    int i    = id    +    1   ; i    <= n   ;    ++i    )    {  
              vis   [i   ]    =    1   ;  
           maxx    -=    a   [i   ];  
              dfs(i   , sum    +    1   );  
              vis   [i   ]    =    0   ;  
           maxx    +=    a   [i   ];  
          }  
   }  

   int    main()  
   {  
          read(n   );  
          read(m   );  
          for    (    int i    =    1   ; i    <= n   ;    ++i    )    {  
              read(   a   [i   ]);  
           maxx    +=    a   [i   ];  
          }  
          sort(a    +    1   , a    + n    +    1   );  
          dfs(   0   ,    1   );  
       cout    << maxn    << endl   ;  
          return    0   ;  
   }  