1 /* 2 将01背包，完全背包，和多重完全背包问题结合起来，那么就是混合三种背的问题 3 根据三种背包的思想，那么可以得到 4 混合三种背包的问题可以这样子求解 5 for(int i=1; i<=N; ++i) 6 if(第i件物品是01背包) 7     zeroOnePack(c[i],w[i]); 8 else if(第i件物品是完全背包) 9     completePack(c[i],w[i]);10 else if(第i件物品是多重完全背包)11     multiplePack(c[i],w[i],n[i]);12 13 这样能得到最优解的原因是，因为前一层已经是得到最优解了，14 当前层求解最优解的时候，我们考虑要使用三种背包中的哪一种方法15 而不用考虑前一层是怎么得到最优解的16 */17 18 #include 
     
      19 #include 
      
       20 int cash;21 int n[11],dk[11];22 int dp[1000000];23 inline int max(const int &a, const int &b)24 {25     return a < b ? b : a;26 }27 void CompletePack(int cost)28 {29     for(int i=cost; i<=cash; ++i)30         dp[i] = max(dp[i],dp[i-cost]+cost);31 }32 void ZeroOnePack(int cost)33 {34     for(int i=cash; i>=cost; --i)35         dp[i] = max(dp[i],dp[i-cost]+cost);36 }37 void MultiplePack(int cnt, int cost)38 {39     if(cnt*cost >=cash)//如果第i种物品的费用总和超过背包容量，那么就是完全背包问题40         CompletePack(cost);41     else42     {43         int k = 1;//二进制拆分44         while(k