【动态规划】01背包问题
01背包問題
問題描述
給定 N 種物品和一個(gè)最大載重量為 C 的背包，物品 i 的重量是 wi，其價(jià)值為 vi 。 問：應(yīng)該如何選擇裝入背包的物品，使得裝入背包中的物品的總價(jià)值最大？問題分析
對(duì)于每個(gè)物品，只能選擇裝或者不裝，不能選擇只裝物體的一部分，因此不能使用單位重量的價(jià)值進(jìn)行排序的方法(貪心)來解決，需要用到動(dòng)態(tài)規(guī)劃來解決。
動(dòng)態(tài)規(guī)劃的三個(gè)核心
對(duì)于該問題而言，由于第i+1件物品只有兩種選擇（選與不選），因此前i+1件產(chǎn)品的最優(yōu)解就是前，子結(jié)構(gòu)就是前i件物品裝在承重為j的容器中，可以用result[i][j]來表示。
邊界就是在只裝第一件物品時(shí)的情況。
通過上面的對(duì)子結(jié)構(gòu)的分析，可以得到狀態(tài)轉(zhuǎn)移方程：
1. j < w[i]時(shí)，即剩余載重量不足以裝下當(dāng)前物品，應(yīng)有最優(yōu)解即是前i-1件時(shí)的解，result[i][j] = result[i-1][j]
2. j >= w[i]時(shí)，即還可以裝下當(dāng)前物品，因此解應(yīng)為 裝與不裝 當(dāng)前物品兩種情況中的最大解。如果不裝，即result[i-1][j]；如果裝,，即result[i-1][j-w[i]] + v[i]。因此取最大值結(jié)果為result[i][j] = max( result[i-1][j], result[i-1][j-w[i]] + v[i] )。
代碼
1.二維數(shù)組
int getLargestValue_1( vector<int> & v, vector<int> & w, int c ) {vector< vector<int> > res( N+1, vector<int>( c+1, 0 ) );/* 該處初始化邊界可以省略由于開始的一列為0，不影響結(jié)果 *//*for( int i = 1; i <= c; i++ ) {if( i < w[i] ) {res[1][i] = 0;} else {res[1][i] = v[1];}}*/for( int i = 1; i <= N; i++ ) { //遍歷所有物品for( int j = 1; j <= c; j++ ) { //遍歷容器容量if( j < w[i] ) { //放不下res[i][j] = res[i-1][j];} else { //放的下res[i][j] = max( res[i-1][j], res[i-1][j-w[i]] + v[i] );}}/* 輸出遍歷每件物品的結(jié)果 *//* for( int j = 1; j <= c; j++ ) {cout << res[i][j] << ' ';}cout << endl; */}return res[N][c]; }2.兩個(gè)一維數(shù)組
由于每次遍歷之用到了當(dāng)前行與上一行，因此可優(yōu)化空間到兩個(gè)一維數(shù)組。
int getLargestValue_2( vector<int> & v, vector<int> & w, int c ) {vector<int> preResult( c+1, 0 ); //存儲(chǔ)上次得到的結(jié)果，對(duì)應(yīng)上一行vector<int> result( c+1, 0 ); //存儲(chǔ)當(dāng)前行結(jié)果for( int i = 1; i <= N; i++ ) {for( int j = 1; j <= c; j++ ) {if( j < w[i] ) {result[j] = preResult[j];} else {result[j] = max( preResult[j], preResult[j-w[i]] + v[i] );}}for( int j = 1; j <= c; j++ ) {cout << preResult[j] << ' ';}cout << endl;preResult = result;}return result[c]; }3. 一維數(shù)組
我們還可以發(fā)現(xiàn)每次使用的都是上一行當(dāng)前列元素上面與左面的元素（preResult[j], preResult[j-w[i]] ），因此我們可以將每行的遍歷順序改變，即從右向左計(jì)算，即可將每次的計(jì)算結(jié)果直接覆蓋到當(dāng)前位置。
int getLargestValue_3( vector<int> & v, vector<int> & w, int c ) {vector<int> result( c+1, 0 );for( int i = 1; i <= N; i++ ) {for( int j = c; j > 0; j-- ) { //從右向左計(jì)算if( j >= w[i] ) {result[j] = max( result[j], result[j-w[i]] + v[i] );}}}return result[c]; }可以使用以下代碼測(cè)試：
int main() {vector<int> v{0, 8, 10, 6, 3, 7, 2}; //價(jià)值vector<int> w{0, 4, 6, 2, 2, 5, 1}; //重量int c = 12; //最大承載重量cout << getLargestValue_3( v, w, c ) << endl;return 0; }最終答案為24。
總結(jié)
以上是生活随笔為你收集整理的【动态规划】01背包问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
