動(dòng)態(tài)規(guī)劃：01背包問(wèn)題-創(chuàng)新互聯(lián)

一、什么是01背包問(wèn)題？

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

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

? 核心思想：

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

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

對(duì)于第二種情況我們很難計(jì)算，因此需要思考從另一個(gè)角度解決問(wèn)題。當(dāng)選擇1~i個(gè)物品，總體積不大于j的集合的大值可以轉(zhuǎn)化成選擇1~i-1個(gè)物品，總體積不大于j-V[i]的集合+最后一個(gè)物品的價(jià)值：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開(kāi)始遍歷，因?yàn)槿绻鹖或j不管哪個(gè)為0,f[i][j]其實(shí)都等于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] 是沒(méi)有用的。

所以第二層循環(huán)可以直接從v[i] 開(kā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)時(shí)遞增的，則是錯(cuò)誤的

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 這一層，即物品只有一件，不存在單件物品滿足價(jià)值為6,8,10的，所以已經(jīng)出錯(cuò)了。

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

例如，一維狀態(tài)第i輪對(duì)體積為 3?的物品進(jìn)行決策，則f[7]由f[4]更新而來(lái)，這里的f[4]正確應(yīng)該是f[i - 1][4]，但從小到大枚舉j這里的f[4]在第i輪計(jì)算卻變成了f[i][4]。當(dāng)逆序枚舉背包容量j時(shí)，我們求f[7]同樣由f[4]更新，但由于是逆序，這里的f[4]還沒(méi)有在第i輪計(jì)算，所以此時(shí)實(shí)際計(jì)算的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)沒(méi)有錯(cuò)誤，即逆序就可以解決這個(gè)優(yōu)化的問(wèn)題了?

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

文章名稱：動(dòng)態(tài)規(guī)劃：01背包問(wèn)題-創(chuàng)新互聯(lián)
分享網(wǎng)址：http://muchs.cn/article12/eisdc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信公眾號(hào)、外貿(mào)建站、建站公司、品牌網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)、Google

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容