背包問題——01背包
01背包作為動態規劃（dynamic programing）中最基礎的問題，需要我們徹底理解其中的原理，為以后解決更難的動態規劃問題打下良好的基礎，
這里擬定一個01背包問題：
有四件不同的物品，一個體積為8的背包，將四件物品中的任意件裝入背包，求背包的最大價值，（注意每件物品有且僅有一件）
為便于觀察，右表中顏色分別與對應左表對應，而灰色部分會在稍后作出解釋，
先上代碼，通過代碼和圖片聯系的方式理解01背包問題
#include<bits/stdc++.h>
using namespace std;
#define N 1010
int a[N],b[N],dp[N],n,v;
int main() {
cin>>n>>v;
for(int i=1; i<=n; i++) {
cin>>a[i]>>b[i];
for(int j=1; j<=v; j++) {
dp[j]=0;
}
}
for(int i=1; i<=n; i++) {
for(int j=v; j>=a[i]; j--) {
dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
}
}
cout<<dp[v]<<endl;
}
代碼運行的程序中dp每行更新的狀態（從后往前更新，即每行由8到1遍歷）
代碼核心：狀態轉移方程
for(int i=1; i<=n; i++) {
for(int j=v; j>=a[i]; j--) {
dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
}
}
接下來具體描述代碼的運行程序：
首先我們要明白代碼是從紅色標記的（1，8）開始的，而且灰色部分在每輪的 i 回圈中是不會被訪問的
原因在這里：
for(int j=v; j>=a[i]; j--)
不難看出每次的 j 回圈都是從最大體積 v（8）開始的，當體積變數 j < a[ i ]時背包無法裝下當前物品，相當于沒有進去入新的物品的可能性，不予處理，
由于第一行只有一個體積為2價值為3的物品，所以第一行（j >= a[ 1 ]）的情況下，dp[ j ]從后到前最大值一直是3，
在第二行的開始（j = 8 處），我們可以看到dp[ j ]提高到了7，這個7是怎么來的呢？
回到狀態轉移方程：
dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
將實時變數帶入：
dp[8]=max(dp[8],dp[8-3]+4);
而其中的dp[ 8 - 3 ]就是圖中第一行的紫色塊，它存的值為3，3+4=7, 7從此來，我們繼續往前遍歷，保證 dp 陣列得到及時更新，
在經過多次 i 回圈之后，在dp[ v ]即dp[ 8 ]處得到結果10，
以上即為一個簡單01背包問題代碼的大致運行程序，希望大家可以從中有所識訓，加油！代碼人！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/257874.html
標籤：其他
下一篇：EOJ 3294. WiFi