本文講解01背包問題的動(dòng)態(tài)規(guī)劃求解，并使用C++進(jìn)行了實(shí)現(xiàn)

文章目錄

• 01背包問題
• 動(dòng)態(tài)規(guī)劃
• 01背包問題的動(dòng)態(tài)規(guī)劃求解
• 01背包問題的動(dòng)態(tài)規(guī)劃求解-C++實(shí)現(xiàn)

01背包問題

有$n$個(gè)物品，這些物品的重量分別為$w_1,w_2,...,w_n$，價(jià)值分別為$v_1,v_2,...,v_n$.

現(xiàn)給定一個(gè)背包，背包的容量為$C$，要求從這個(gè)$n$個(gè)物品中選擇一些物品裝進(jìn)背包，讓背包盡可能裝滿，并使得背包里裝的物品的價(jià)值最大。

要從這些物品中挑選一些裝進(jìn)背包，對(duì)于某一物品而言，只有裝和不裝兩種選擇，因此稱為01背包問題

動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃是一種算法設(shè)計(jì)技術(shù)，它用來解決類似這樣的問題：

一個(gè)問題可以被分成很多個(gè)階段，而且任何一階段的行為都依賴于該階段前面的狀態(tài)，但是該階段前面的狀態(tài)是如何得來的與該階段無關(guān)。我們稱這樣的過程為多階段決策過程。

事實(shí)上，動(dòng)態(tài)規(guī)劃就是解決多段決策過程最優(yōu)問題的一種方法。

在使用動(dòng)態(tài)規(guī)劃法求解問題時(shí)，被求解的問題應(yīng)滿足最優(yōu)性原則：

一個(gè)最優(yōu)問題的任何實(shí)例的最優(yōu)解是由該實(shí)例的子實(shí)例的最優(yōu)解組成的(子問題最優(yōu)，全局才能最優(yōu))。

拿斐波那契數(shù)列來說：

• 如果我們直接使用遞歸表達(dá)式求解的話回耗費(fèi)很大內(nèi)存且會(huì)被重復(fù)計(jì)算
• 而如果我們正向計(jì)算，把每一次計(jì)算的結(jié)果保存起來，則只需要進(jìn)行加法運(yùn)算，則大大地方便了計(jì)算

因此，對(duì)于交疊子問題的求解，我們也可以使用這種方式：

對(duì)交疊子問題的每個(gè)較小子問題求解一次后記錄在表中，就可以從表中得到原始問題的解

01背包問題的動(dòng)態(tài)規(guī)劃求解

我們這里舉例說明背包問題的動(dòng)態(tài)規(guī)劃求解

背包容量為5，各種物品的重量及價(jià)值如下：

物品重量價(jià)值

1	2	12
2	1	10
3	3	20
4	2	15

正如前面我們所分析的，我們通過填表的方式利用動(dòng)態(tài)規(guī)劃的方式求解的話能夠大大地簡化問題的求解：

我們用$V(i,j)$表示將前i個(gè)物品放到容量為j的背包中時(shí)最優(yōu)解的物品總價(jià)值，則在裝入物品的時(shí)候我們有兩種情況：

第i個(gè)物品不能被放入背包，則背包的價(jià)值為原先沒有裝入第i個(gè)物品時(shí)的價(jià)值：
$$V(i,j)=V(i?1,j)$$

可將物品放入背包，應(yīng)對(duì)放入物品放入背包后的情況進(jìn)行評(píng)估，如果放入后背包的價(jià)值增加，則放入，否則不放入，價(jià)值為原來的沒有放入時(shí)的價(jià)值：
$$V(i,j)=max\{V(i?1,j),v_i+V(i?1,j?w_i)\}$$

即：

我們對(duì)背包容量為0到5填表，得到表的情況如下：

重量價(jià)值$i$\ $j$012345

		0	0	0	0	0	0	0
2	12	1	0	0	12	12	12	12
1	10	2	0	10	12	22	22	22
3	20	3	0	10	12	22	30	32
2	15	4	0	10	15	25	30	37

最終的最優(yōu)解為表的后一個(gè)元素37

01背包問題的動(dòng)態(tài)規(guī)劃求解-C++實(shí)現(xiàn)

#include <iostream> using namespace std; int knapsack(int num,int capacity,int weight[],int value[]){//使用動(dòng)態(tài)規(guī)劃求解0-1背包問題/*@parameters:@num:物品數(shù)量，整數(shù)類型@capacity:背包容量，整數(shù)類型@weight:各個(gè)物品的重量，數(shù)組類型@value:各個(gè)物品的價(jià)值，數(shù)組類型*/int space,sub_cap,total_value[num+1][capacity+1];for(int i=0;i<=num;i++)for(int j=0;j<=capacity;j++)total_value[i][j]=0;//初始化記憶表格for(sub_cap=1;sub_cap<=capacity;sub_cap++){for(space=1;space<=num;space++){if(sub_cap>=weight[space-1]){//判斷是否能不能裝下//能裝下，判斷裝了以后是不是背包的價(jià)值更大了total_value[space][sub_cap]=max(total_value[space-1][sub_cap],total_value[space-1][sub_cap-weight[space-1]]+value[space-1]);}else{//裝不下的話背包價(jià)值還是沒有裝之前的價(jià)值total_value[space][sub_cap]=total_value[space-1][sub_cap];}}}return total_value[num][capacity]; } int main(){int num=4,capacity=5,weight[]={2,1,3,2},value[]={12,10,20,15};cout<<knapsack(num,capacity,weight,value);return 0; }

代碼的運(yùn)行結(jié)果為：

37

才疏學(xué)淺，難免有錯(cuò)誤和不當(dāng)之處，歡迎交流批評(píng)指正!
同時(shí)有問題的話歡迎留言或郵箱聯(lián)系（ljt_IT@163.com）。

創(chuàng)作不易，覺得寫得不錯(cuò)就微信掃碼獎(jiǎng)勵(lì)一下吧！

總結(jié)

以上是生活随笔為你收集整理的01背包问题的动态规划求解及其C++实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。