一、問題描述

二、思路分析

這道題同樣是背包問題，那么它也同樣滿足三個性質(zhì)：重疊子問題、最優(yōu)子結構以及無后效性。那么這樣的話，我們依然可以使用動態(tài)規(guī)劃的思路去分析這道題目。那么動態(tài)規(guī)劃的分析主要分為兩步：狀態(tài)轉移方程的書寫以及循環(huán)的設計。

1、狀態(tài)轉移方程

（1）狀態(tài)表示：

我們在前面的兩篇文章中介紹過，對于背包問題而言，我們一般用一個二維數(shù)組來表示dp數(shù)組，即我們經(jīng)常寫的：$f(i,j)$

那么$f(i,j)$的意思是，當物品數(shù)量為$i$，自己的背包容量是$j$的時候，我們所能攜帶的最大價值：$f[i][j]$。

（2）狀態(tài)轉移：

狀態(tài)轉移的目的是為了能夠?qū)⒋笠?guī)模的問題轉化成較小規(guī)模的問題。

背包問題中，狀態(tài)轉移方程的書寫就一個技巧：活在當下

我們此時共用$i$個物品，我們不可能一下子就同時做出多個決策，從而得到最優(yōu)解。我們就看眼前，我們眼前的就是第$i$個物品，而我們要做的決策就是，第$i$個物品到底選不選，選的話，在背包容量允許的條件下，我們選幾個？

如果我們不選的話，我們就能寫出下列的方程：

$$f(i,j)=f(i?1,j)$$

由于我們不選第$i$個物品，所以我們只需要考慮前$i?1$個。這樣我們就把規(guī)模從$i$降低到了$i?1$。

假設我們選的話，那么就能夠?qū)懗上铝行问剑海?span id="n5n3t3z" class="katex--inline">$v[i]$表示第$i$個物品的體積，$w[i]$表示第$i$個物品的價值）

$$f(i,j)=f(i?1,j?v[i]?k)+w[i]?k$$

上述等式成立的前提是保證：$j\ge v[i]?k$

我們只需要在上述的這些情況中取一個最大值即可：

所以我們的狀態(tài)轉移方程可以表示為：

$$f(i,j)=max?\begin{array}{ll}f(i?1,j)& \\ f(i?1,j?v[i])+w[i]& j\ge v[i]\\ f(i?1,j?v[i]?2)+w[i]?2& j\ge v[i]?2\\ ......& \\ f(i?1,j?v[i]?k)+w[i]?k& j\ge v[i]?k\end{array}$$

2、循環(huán)設計

我們的循環(huán)和之前所介紹的01背包問題、完全背包問題的循環(huán)設計是一樣的，最外層循環(huán)是背包的規(guī)模從小到大，第二層的循環(huán)是背包的容量，從小到大。

三、代碼模板

1、樸素版

我們綜合上面的思路，就能夠?qū)懗鱿旅娴拇a：

#include<iostream>
using namespace std;
const int N=110;
int f[N][N],v[N],w[N],q[N];
int n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",v+i,w+i,q+i);
    }
    for(int i=1;i<=n;i++)//枚舉物品規(guī)模
    {
        for(int j=0;j<=m;j++)//枚舉背包容量
        {
            for(int k=0;k*v[i]<=j&&k<=q[i];k++)//書寫狀態(tài)轉移方程
            {
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

2、優(yōu)化版

我們發(fā)現(xiàn)上面的這個樸素版代碼包含了三重循環(huán)，那么我們?nèi)绾谓档鸵粚友h(huán)呢？

其實，我們的多重背包可以轉化成01背包問題。這樣講肯定很抽象，大家可以看下面的圖：

但是這樣做的話只是形式上做了優(yōu)化，從$n^3$到$n^2$，但實際上依舊是一個$n^3$的時間復雜度。

而這樣沒有成功優(yōu)化的原因是因為我們有$n$個$i$物品，就需要重復$n$個i物品。那么我們是否存在一種方式，我們不需要枚舉$n$次i物品，就能夠表示$n$個$i$物品呢？

答案是有的。

我們的十進制數(shù)可以用二進制數(shù)來表示。

假設我們的二進制位有4位：

那么我們能表示的范圍是：$0000$ ~ $1111$。

而

$1111=1000+0100+0010+0001$

上面右側的四個部分組成了這個數(shù)字。

我們可以從形式上掌握一下，這個四個部分所代表的含義就是對應的位數(shù)是1。

$1000$：第四位是1
$0100$：第三位是1
$0010$：第二位是1
$0001$：第一位是1

接著我們發(fā)現(xiàn)，$0000$到$1111$之間的任何一個數(shù)字，其實無非是某位是0，某位是1。如果某位是1，我們只需要加上上面四個數(shù)字中的其中一個。

例如：
$1001=1000+0001$
$1101=1000+0001+0100$

因此我們就能夠得到一個結論，我們能夠有這四個數(shù)字表示$0000$到$1111$之間的所有數(shù)字。

轉換成十進制而言，就是說我們能夠用$1$,$2$,$4$,$8$表示出$0$到$15$之間的任何數(shù)字。

所以，我們可以利用幾個$2^k$，其中，來表達一個范圍內(nèi)的所有數(shù)字。根據(jù)我們剛才的推導，所能表示的范圍其實就是我們剛剛這幾個數(shù)加在一起時的值，其實就是一個等比數(shù)列求和。

用數(shù)學公式表達就是

我們可以利用：表示$0$ ~ 2^(k+1)$?1$之間的所有數(shù)字。

那么如果我們的要表達的200

那么我們可以利用：

這幾個數(shù)能表達的最大值是：$2^7?1=127$

那么從128到200怎么表示呢？

其實我們只需要多加一個73即可。

也就是說，我們可以用：

來表達0-200。

為什么呢？

我們只用前面的這些$2^k$。那么我們能表示的是$0?127$。
如果我們每次選擇的時候都加上一個73，我們能表示的范圍就是：
$73?200$

雖然兩部分之間有一點重疊的部分，但是重疊的話，無非就是我們重復計算了幾個相同情況而已，并不影響我們結果的正確性。

那么我們發(fā)現(xiàn)，此時我們利用$O(logn)$級別的數(shù)字表示了$O(n)$。

時間上做了非常大的優(yōu)化。

而這種優(yōu)化方式被稱作二進制優(yōu)化。

如圖所示：

根據(jù)上面的思路，我們就能夠?qū)懗鱿旅娴膬?yōu)化版本的代碼：文章來源地址http://www.zghlxwxcb.cn/news/detail-621491.html

#include<iostream>
using namespace std;
const int N=3e4+10;
int dp[N],v[N],w[N];
int n,m;
int main()
{
    cin>>n>>m;
    int cnt=1;
    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        int k=1;
        //進行 “打包” 轉換：二進制優(yōu)化，轉換成01背包
        while(k<c)
        {
            v[cnt]=k*a,w[cnt++]=k*b;
            c-=k;
            k*=2;
        }
        if(c>0)
            v[cnt]=c*a,w[cnt++]=c*b;
    }
    //利用01背包中的空間優(yōu)化模板求解。
    for(int i=1;i<=cnt;i++)
        for(int j=m;j>=v[i];j--)
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    cout<<dp[m]<<endl;
    return 0;
}

到了這里，關于多重背包問題（詳解二進制優(yōu)化原理）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！