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

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

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

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

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

舉例

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

圖解這個例子：

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

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

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

根據(jù)這三個情況，我們很容易得出狀態(tài)轉(zhuǎn)移方程，我們設(shè)限制重量為v1，當(dāng)前重量為v2，當(dāng)前價值為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背包代碼實現(xiàn)

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

#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級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

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

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供動態(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)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)