動態規劃之0-1揹包問題技术頭條網

動態規劃之0-1揹包問題

2020-03-22 00:01:42 YoungPi

作為動態規劃模型中一個經典模型。它既簡單形象容易理解，又在某種程度上能夠揭示動態規劃的本質，故不少教材都把它作為動態規劃部分的第一道例題.

題目要求

有N件物品和一個容量為V的揹包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入揹包可使這些物品的費用總和不超過揹包容量，且價值總和最大。

輸入格式

第一行兩個整數，N,M空格隔開，分別表示物品數量和揹包容積。

接下來有N行,每行兩個整數vi,wi,空格隔開,分別表示第i件物品的體積和價格

輸出格式

輸出一個整數，表示最大價值。

數據範圍

輸入樣例

<code>4 5
1 2
2 4
3 4
4 5
/<code>

輸出樣例：

<code>8/<code>

分析過程

0/1揹包問題是最基本的揹包問題，每個物品最多隻能放一次或者選擇不放。

思路A：一共有n個東西，揹包容量為m，對於每個物品我們有兩種選擇方案，一個物品有兩種，兩個物品有四種，三個物品有八種，那麼n個物品就有2^n種方案。窮舉這2^n種方案，當n=100的時候，等於多少？2的一百次方等於：1.26*10^30 這個數值是非常大的，例如存在一張可以充分摺疊的紙厚度為0.1毫米，對半折一次，則厚度是0.2mm，再對摺一次，是0.4mm……由此類推，對摺n次，那麼紙的厚度是：(2^n)×0.1mm 這個厚度的增長將呈指數增長的趨勢，那麼折了100次後，那麼其長度到“134億光年”，而宇宙大爆炸至今的全部時間僅僅才137億年。扯遠了，就是為了說明這個窮舉法不可取。

思路B：動態規劃的思想本質就是找到遞歸的表達式。在找遞歸的表達式的時候肯定是存在一定的邊界限制（如青蛙跳臺階這種題目就沒有限制）

那麼這道題它給出了一個邊界限制：容量M，當容量滿的時候就再也放不下東西了，故我們在進行遞歸的時候需要考慮當前的容量，這就是我們的限制條件目標函數是什麼？目標函數就是我們的價值最大化max(value)

這個遞歸函數要怎麼寫？ 這道題我打算用一維數組的做法來做，我先初始化一個數組叫f，長度為m+1(為了索引從1-m代表著容量從1-m),最後取f的最後一個元素即為答案。那麼這個遞歸函數就可以表示為f(m)=max(f(m),f(m-w[i])+v[i])

f(m) 當前揹包容量為m的情況下不選擇當前物品

f(m-w[i])+v[i] 當前揹包容量為m情況下選擇當前物品

m-w[i]代表著我這個揹包在上一次選擇中必須至少給我留下w[i]的空間，我才可以選擇當前物品，然後得到它的價值v[i]

解題步驟

首先初始化f，將重量放到一個數組W(weighted)中，將價值放到一個數組V(value)中

其次開始遍歷我的物品，一共n個，遍歷我每一個物品的時候我都會使得我的揹包容量依次遞增（從1到m）。這一步什麼意思？我們來舉個例子容量從1開始一直遞增，假設第一個物品的weight=1,value=2,那麼容量為1的時候f[1]=2，容量為2的時候f[2]=4 f[3]=6 ...??? 好像走錯片場了。我們這個問題的前提是每個物品只能選擇一次或者不選擇使得利益最大化，那如果這個揹包容量容量從1開始一直遞增，我們這個問題就變成了每個物品可以選擇多次。

為什麼會變成這種情況，因為揹包容量如果從少到多，它每次貪心max()的時候都會想，我還能不能放入更多的這個物品，現在放入一件了，能不能再放多一件。

怎麼修改？把容量從m到1一直遞減就可以了。f[m]=2,f[m-1]=2...f[1]=2 這種情況，因為揹包容量如果從多到少，它每次貪心max()的時候，都是先看能不能放下一件當前物品,不會產生放置兩件物品以上的情況。

最後我們把f輸出，取最後一個元素即可

注意：分歧其實就在f[m-w[i]]，

如果容量從小到大遍歷，那麼到最後的f[m]取決的結果不是基於上一物品選擇,而是取決於當前物品的選擇

如果容量從大到小遍歷，那麼到最後的f[m]取決的結果是基於上一物品選擇

c++實現

<code>#include<bits>
using namespace std;
const int N=1010;

int f[N];
int v[N],w[N];
int n,m;
int main(){
    cin>>n>>m;

    for(int i=0;i        cin>>v[i]>>w[i];
    }

    for(int i=0;i 
        for(int j=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<}/<bits>/<code>