多重背包

問題描述：給定\(n\)種物品和一個體積為\(V\)的背包，第\(i\)種物品數量為\(m_i\)，體積為\(c_i\)，價值為\(w_i\)。如何裝填背包使總價值最大？

通過直接求解，轉移方程式：\(dp[i][j]=\max(dp[i-1][j],dp[i-1][j-k\times c[i]]+k\times w[i]),k\in[1,\min(m[i],\frac{j}{c[i]})]\)。復雜度\(O(V\sum\limits_{i=1}^n m_i)\)，超時。

實際上，多重背包屬于\(0/1\)背包的推廣，易得其可轉換為\(0/1\)背包問題：將第\(i\)種物品視為\(m_i\)種獨立(不同)的物品，并按\(0/1\)背包求解。定義狀態數組\(dp[i][j]\)，表示將前\(i\)個物品放入容積為\(j\)的背包時的最大價值。實際上復雜度不變，仍為\(O(V\sum\limits_{i=1}^n m_i)\)，超時。

int dp[n+1][V+1],c[n],w[n],m[n];
int MultiplePack(){
    for(int i=0;i<=n;i++) dp[i][0]=0;
    for(int i=0;i<=V;i++) dp[0][i]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=V;j++)
            for(int k=1;k<=m[i]&&k*c[i]<=j;k++)
                dp[i][j]=max(dp[i][j],dp[i-1][j-k*c[i]]+k*w[i]);
    return dp[n][V];
}

二進制優化

原理：倍增。任意十進制整數均可使用2的冪次經過有限次相加得到，以\(2^i(i\in[0,\lceil\log_2m_i\rceil+1])\)順次拆分，最后可能有一個余數。因此使用倍增即可將第\(i\)種物品變為\(\log_2m_i\)個，每個物品體積為\(2^k\times c_i\)，價值為\(2^k\times w_i\)。

以下為二進制拆分代碼，之后使用new_n、new_c、new_w以\(0/1\)背包求解即可。復雜度\(O(V\sum\limits_{i=1}^n \log_2m_i)\)。

int new_n=0,new_c[N],new_w[N];
for(int i=1;i<=n;i++){//遍歷每種物品
    for(int j=1;j<=m[i];j<<=1){//遍歷每種物品的個數
        new_n++;
        m[i]-=j;
        new_c[new_n]=j*c[i];
        new_w[new_n]=j*w[i];
    }
    if(m[i]){//若有余數
        new_n++;
        new_c[new_n]=m[i]*c[i];
        new_w[new_n]=m[i]*w[i];
    }
}

單調隊列優化