背包問題2 多重背包，混合背包

多重背包

 有總體積為V的背包，存在n個物品，體積為 v i v_i vi​，價值為 w i w_i wi​，數量為 c i c_i ci​，求怎麼放可以得到最大體積

多重背包問題有三種解法：1、轉換為01背包 2、二進制分解 3、單調隊列優化，一般采用二進制分解。

1、轉換為01背包，做法和完全背包轉01背包類似，我們之前講過了。

const int n=1010;
int dp[n];
int Multiple_pack(vector<int>&v, vector<int>&w,vector<int> c, int V)
{
  dp[0]=0;
  for(int i=0;i<v.size();i++)
  {
    for(int j=V;j>=v[i];j--)
    {
      for(int k=0;k<=c[i]&&k<=j/v[i],k++)
      {
        dp[j]=max(dp[j],dp[j-K*v[i]]+k*w[i]);
      }
    }
  }
  return dp[V];
}
           

時間複雜度為 O ( n V K ) O(nVK) O(nVK)，空間複雜度為 O ( V ) O(V) O(V)

 2、二進制分解可以對時間複雜度進行優化，優化為 O ( n V l o g ( c ) ) O(nVlog(c)) O(nVlog(c))。二進制分解的原理就是用一系列二進制數或者在加一個數可以表示指定的一個數。

比如12 可以用（1 2 4 5）進行表示

1 → 1 , 2 → 2 , 1 + 2 → 3 , 4 → 4 , 1 + 4 → 5 , 1 + 5 → 6 , 2 + 5 → 7 , 1 + 2 + 5 → 8 1\rightarrow1,2\rightarrow2,1+2\rightarrow3,4\rightarrow4,1+4\rightarrow5,1+5\rightarrow6,2+5\rightarrow7,1+2+5\rightarrow8 1→1,2→2,1+2→3,4→4,1+4→5,1+5→6,2+5→7,1+2+5→8

4 + 5 → 9 , 1 + 4 + 5 → 10 , 2 + 4 + 5 → 11 , 1 + 2 + 4 + 5 → 12 4+5\rightarrow9,1+4+5\rightarrow10,2+4+5\rightarrow11,1+2+4+5\rightarrow12 4+5→9,1+4+5→10,2+4+5→11,1+2+4+5→12

 是以通過一系列二進制數，就可以實作對多重背包的優化。

const int n=1010;
int dp[n];
//因為多重背包會調用01背包，我們這裡先給出01背包，完全背包的函數
void Zero_one_pack(int v_i, int w_i,int V) 
{
   for(int i=V;i>=v[i];i--)
      {
        dp[i]=max(dp[i],dp[i-v[i]]+w[i]);
      }  
}
void Complete_pack(int v_i, int w_i,int V) 
{
   for(int i=v[i];i<=V;i++)
      {
        dp[i]=max(dp[i],dp[i-v[i]]+w[i]);
      }  
}
int Op1_Multiple_pack(vector<int>&v, vector<int>&w,vector<int> c, int V)
{
  dp[0]=0;
  for(int i=0;i<v.size();i++)
  {
  //當c[i]的數大于等于允許的最大數量，則直接進行完全背包
    if(V/v[i]<=c[i])
    {
      Complete_pack(v[i], w[i],V);
      continue;
    }
     //否則進行二進制優化
    for(int j=1;j<=c[i];j*=2)
    {
    //對其進行等價的01背包
        c[i]-=j;
       Zero_one_pack(j*v[i],j*w[i],V);
    }
     //有可能還剩下一個不是二進制的數，如我們的例子中的5，對其繼續進行01背包
       Zero_one_pack(c[i]*v[i],c[i]*w[i],V);
  }
      return dp[V];
}
           

時間複雜為 O ( n V l o g ( c ) ) O(nVlog(c)) O(nVlog(c))

混合背包

 有總體積為V的背包，存在n個物品，體積為 v i v_i vi​，價值為 w i w_i wi​，數量分為三種，

  − 1 -1 −1表示隻有1個（01背包）

  0 0 0表示數量為無限個（完全背包）

  c i c_i ci​表示有 c i c_i ci​個數量（多重背包）

 做法就是對其進行分情況讨論，按照我們之前的做法，多重背包問題和01背包問題按01背包的解法做，完全背包按完全背包的解法做。

int v=1010;
int dp[n];
void Zero_one_pack(int v_i, int w_i,int V) 
{
   for(int i=V;i>=v[i];i--)
      {
        dp[i]=max(dp[i],dp[i-v[i]]+w[i]);
      }  
}
void Complete_pack(int v_i, int w_i,int V) 
{
   for(int i=v[i];i<=V;i++)
      {
        dp[i]=max(dp[i],dp[i-v[i]]+w[i]);
      }  
}
int Op1_Multiple_pack(vector<int>&v, vector<int>&w,vector<int> c, int V)
{
  for(int i=0;i<v.size(); i++)
  {
      if(c[i]==0)
      {
         //完全背包
         Complete_pack(v[i],w[i],V);
      }
      else if(c[i]==-1)
      {
         //01背包
         Zero_one_pack(v[i],w[i],V);
      }
      else
      {
        //多重背包問題二進制分解在做01背包
         for(int j=1;j<=c[i];j*=2)
          {
            c[i]-=j;
            Zero_one_pack(j*v[i],j*w[i],V);
          }
     //有可能還剩下一個不是二進制的數，對其繼續進行01背包
            Zero_one_pack(c[i]*v[i],c[i]*w[i],V);
       }  
  }
  return dp[V];
}