一、什么是01背包問題？

舉個例子，你要去一個水果攤拿水果，每種水果都有對應(yīng)的兩種屬性：占用的體積V和蘊含的價值W。而你的背包體積為N。老板說：每種水果只能拿一個！因此對于咱們肯定得想一種搭配方式使得拿的水果總體積不超過背包容積，但是價值總和達到大！

堅守“ 做人真誠 · 做事靠譜 · 口碑至上 · 高效敬業(yè) ”的價值觀，專業(yè)網(wǎng)站建設(shè)服務(wù)10余年為成都成都銅雕雕塑小微創(chuàng)業(yè)公司專業(yè)提供成都企業(yè)網(wǎng)站建設(shè)營銷網(wǎng)站建設(shè)商城網(wǎng)站建設(shè)手機網(wǎng)站建設(shè)小程序網(wǎng)站建設(shè)網(wǎng)站改版，從內(nèi)容策劃、視覺設(shè)計、底層架構(gòu)、網(wǎng)頁布局、功能開發(fā)迭代于一體的高端網(wǎng)站建設(shè)服務(wù)。

? 核心思想：

? f[i][j]:表示所有選法集合中,只從前i個物品中選,并且總體積不大于j的選法的集合,它的值是這個集合中每一個選法的大值。

? 對于01背包問題選擇方法的集合可以分成2種：
①不選第i個物品，并且總體積不大于j的集合所達到的大值:f[i-1][j]
②選擇1~i個物品，并且總體積不大于j的集合所達到的大值f[i][j]

對于第二種情況我們很難計算，因此需要思考從另一個角度解決問題。當(dāng)選擇1~i個物品，總體積不大于j的集合的大值可以轉(zhuǎn)化成選擇1~i-1個物品，總體積不大于j-V[i]的集合+最后一個物品的價值：f[i-1][j-V[i]]+w[i]

因此總結(jié)：f[i][j]= Max{f[i-1][j],f[i-1][j-v[i]]+w[i]}!!! 二、01背包例題

? #ACWing 2

代碼：

二維數(shù)組：

#includeusing namespace std;

const int N=1010;
int v[N],w[N],f[N][N];
int n,m;

int main()
{
  scanf("%d%d",&n,&m);
  
  for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
  
  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
      f[i][j]=f[i-1][j];
      if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
    }    

  printf("%d",f[n][m]); 
  return 0;
}

##注意 ：為什么i和j從1開始遍歷，因為如果i或j不管哪個為0,f[i][j]其實都等于0??！

一維數(shù)組： 優(yōu)化版

#includeusing namespace std;

const int N=1010;
int v[N],w[N],f[N];
int n,m;

int main()
{
  scanf("%d%d",&n,&m);
  
  for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
  
  for(int i=1;i<=n;i++)
    for(int j=m;j>=v[i];j--)
    {
      f[j]=max(f[j],f[j-v[i]]+w[i]);
    }
    
  printf("%d",f[m]);
  return 0;
}

如何優(yōu)化:

? 從二維做法中可以看出f[i] [j]大值的更新只用到了 f[i-1] [j]，即 f[i-2][j] 到 f[0][j] 是沒有用的。

所以第二層循環(huán)可以直接從v[i] 開始。

for (int i = 1; i<= n; i++) {
    for (int j = v[i]; j<= m; j++) {
        f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
    }
}

二維優(yōu)化到一維后：

如果刪掉f[i]這一維，結(jié)果如下：如果j層循環(huán)時遞增的，則是錯誤的

for (int i = 1; i<= n; i++) {
    for (int j = v[i]; j<= m; j++) {
        f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
}

模擬結(jié)果：

可以看出處于 i == 1 這一層，即物品只有一件，不存在單件物品滿足價值為6,8,10的，所以已經(jīng)出錯了。

為什么一維情況下枚舉背包容量需要逆序？
在二維情況下，狀態(tài)f[i][j]是由上一輪i - 1的狀態(tài)得來的，f[i][j]與f[i - 1][j]是獨立的。而優(yōu)化到一維后，如果我們還是正序，則有f[較小體積]更新到f[較大體積]，則有可能本應(yīng)該用第i-1輪的狀態(tài)卻用的是第i輪的狀態(tài)。

例如，一維狀態(tài)第i輪對體積為 3?的物品進行決策，則f[7]由f[4]更新而來，這里的f[4]正確應(yīng)該是f[i - 1][4]，但從小到大枚舉j這里的f[4]在第i輪計算卻變成了f[i][4]。當(dāng)逆序枚舉背包容量j時，我們求f[7]同樣由f[4]更新，但由于是逆序，這里的f[4]還沒有在第i輪計算，所以此時實際計算的f[4]仍然是f[i - 1][4]。

? 如果 j 層循環(huán)是逆序的：

for (int i = 1; i<= n; i++) {
        for (int j = m; j >= v[i]; j--) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

模擬結(jié)果：?

模擬一下發(fā)現(xiàn)沒有錯誤，即逆序就可以解決這個優(yōu)化的問題了?

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站標(biāo)題：動態(tài)規(guī)劃：01背包問題-創(chuàng)新互聯(lián)
分享地址：http://weahome.cn/article/eisdc.html