1 思路

多重背包问题，可以将其化为01背包问题。

若用一般方法必TLE(把n个第i种物品看成毫无关联的n个物品，即∑ n_i i = 1,2…N个物品(N为物品数目))

采用二进制思想，把n个第i种物品拆成1,2,4…2^k,x个（其中x为不能再拆成2ⁿ 次方而余下的）

这样时间时间复杂度便由原来的θ(V×∑ n_i)变为θ(V×∑ log n_i)

2 源码

#include 
       
        #include 
        
                     // sort头文件#include 
         
                        // memset头文件using namespace std;int main(int argc, char *argv[]){    int c, N, v[100];    int dp[100005];    int num, demo, i, j, k;    while(cin>>c>>N){        k = 0;        for(i=0; i
          
           >num>>demo;            j = 1;            while(j
           
            =2^k的最大整数。如果为13，就拆为1 2 4 6。                num -= j;                v[k++] = j * demo;                j *= 2;            }            if(num)             // 此时不能正好完全拆成2^k形式                v[k++] = num*demo;        }        memset(dp, 0, sizeof(dp));        for(i=0; i
            
             =0; j--) if(j>=v[i]) // 01背包一维数组解法 dp[j] = max(dp[j], dp[j-v[i]]+v[i]); cout<
             
              <
             
            
           
          
         
        
       

Author: visaya fan 

Date: 2011-08-23 00:50:28

HTML generated by org-mode 6.33x in emacs 23