01背包——二維動(dòng)態(tài)規(guī)劃【c++】代碼實(shí)現(xiàn)-創(chuàng)新互聯(lián)

今天學(xué)了01背包，就想來(lái)講一講，正好回顧一下（BZOJ上的題目）。

十多年的加查網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開(kāi)發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。網(wǎng)絡(luò)營(yíng)銷推廣的優(yōu)勢(shì)是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整加查建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無(wú)論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。創(chuàng)新互聯(lián)公司從事“加查網(wǎng)站設(shè)計(jì)”,“加查網(wǎng)站推廣”以來(lái)，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。01背包

所謂01背包，也就是背包的一種，01背包和完全背包的區(qū)別就在于，01背包一件物品只能選擇一次，而完全背包可以重復(fù)選擇某件物品，達(dá)到價(jià)值大化的問(wèn)題，總之，背包問(wèn)題是一種最值問(wèn)題，要求我們找到最優(yōu)解，其實(shí)用到的動(dòng)歸也有點(diǎn)貪心的思想在里面，每次只考慮當(dāng)前和以前，不用考慮未來(lái)。

01背包的動(dòng)態(tài)規(guī)劃思路

關(guān)于用動(dòng)歸解決的這件事呢，首先給出一個(gè)例子吧：

舉例

有一個(gè)小偷，半夜來(lái)到一戶人家偷東西，他帶了一個(gè)背包，這個(gè)背包只容的下4磅的物品，有一下一些物品，每個(gè)物品只有一個(gè)而且不能拆分（順便說(shuō)一句，這是01背包的前提），求出帶走物品的大價(jià)值。

圖解這個(gè)例子：

首先，我們要通過(guò)列表的方式來(lái)實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃，我們先來(lái)看看表格：

很顯然，行是背包的容量，必須從1-n,才能實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃，前面的是在為后面的做鋪墊。
列是各種物品。
在填表的時(shí)候，可能會(huì)遇到一下情況：

1.物品的數(shù)量比背包容量大：
將此格填上0；
2.dp[i - 1][j]格的重量加上這個(gè)物品的重量小于等于所限制數(shù)量：
此格= dp[i - 1][j] + 此物品的數(shù)量
3.dp[i - 1][j]格的重量加上這個(gè)物品的重量大于于所限制數(shù)量：
此格= dp[i - 1][限制重量 - 當(dāng)前重量] + 當(dāng)前價(jià)值

根據(jù)這三個(gè)情況，我們很容易得出狀態(tài)轉(zhuǎn)移方程，我們?cè)O(shè)限制重量為v1，當(dāng)前重量為v2，當(dāng)前價(jià)值為p2

那么：dp [ i ] [ j ] = max( dp [ i - 1 ] [ j ] + p2 , dp [ i - 1] [ v1 - v2 ] + p2)

另外若出現(xiàn)第一種情況，則當(dāng)前格為0；
按照當(dāng)前的規(guī)則，我們可以根據(jù)剛才的例子得出下列表格：

01背包代碼實(shí)現(xiàn)

我們直接通過(guò)上述的遞推式加上兩個(gè)循環(huán)即可了，代碼真的一點(diǎn)也不復(fù)雜，剛學(xué)的時(shí)候01背包這個(gè)名字把我唬住了

#includeusing namespace std;
const int N=1005;              //根據(jù)題目的要求改變
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++)
  	 cin >>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]);
    }    
  cout<< f[m][n];
  return 0;
}

待續(xù)更

你是否還在尋找穩(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)查看詳情吧

名稱欄目：01背包——二維動(dòng)態(tài)規(guī)劃【c++】代碼實(shí)現(xiàn)-創(chuàng)新互聯(lián)
鏈接地址：http://muchs.cn/article16/dsigdg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供動(dòng)態(tài)網(wǎng)站、云服務(wù)器、網(wǎng)站改版、網(wǎng)站導(dǎo)航、網(wǎng)站建設(shè)、定制網(wǎng)站

廣告

聲明：本網(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)