? ? ? ? 如果沒有動態路徑規劃基礎的兄弟可以出去了，這個題目有兩個問題

? ? ? ? 第一問講解：

? ? ? ? 1.定義狀態表示

? ? ? ? 剛開始我做的時候根據我的經驗定義了一個狀態表示dp[i]表示從1到i個物品中選擇的最大價值，但是這個狀態表示有一個明顯的問題，我怎么知道第i個物品可不可以放入背包？

? ? ? ? 所以這個一維的狀態表示顯然是不夠的，在上面的時候其實我們只需要知道第i個物品能不能放入背包其實狀態表示就完全了，故我們用二維的dp[i][j]來進行狀態表示，它表示從1到i個物品中選擇容積小于等于j的最大價值

? ? ? ? 2.狀態轉移方程的推導

? ? ? ? 對于第i個物品我們只有兩種選擇，要么拿要么不拿

? ? ? ? 2.1 當我們不拿時那么我們的dp[i][j]顯然和dp[i-1][j]是相等的

? ? ? ? 2.2 當我們拿時需要先判斷空間夠不夠，如果空間足夠那么

????????????????dp[i][j] = max(dp[i-1][j-v[i]]+w[i],dp[i][j])

????????3.初始化

? ? ? ? 3.1 當i為0時說明沒有物品那么容積小于等于j的最大價值其實就是0

? ? ? ? 3.2 當j為0時說明容積為0那么最大價值也是0

? ? ? ? 4.填表順序

? ? ? ? 觀察狀態轉移方程，我們發現dp[i][j]j會用到前一行的數據（這里是我們后面優化的關鍵），所以我們的填表順序是從上往下、從左往右。

#include<iostream>using namespace std;const int N = 1010;int n,V,v[N],w[N];
int dp[N][N];int main()
{int ret1 = 0;cin>>n>>V;for(int i = 1;i<=n;i++) cin>>v[i]>>w[i];for(int i = 1;i<=n;i++)for(int j = 1;j<=V;j++){dp[i][j] = dp[i-1][j];if(j>=v[i]) dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]]+w[i]);ret1 = max(ret1,dp[i][j]);}cout<<ret1<<endl;return 0;
}

? ? ? ? 第二問講解

? ? ? ? 1.定義狀態表示

? ? ? ? 與第一問很像，但是這是并不是容積小于等于j的最大價值而是容積等于j的最大價值

? ? ? ? 2.狀態轉移方程

? ? ? ? 和第一問差不多，但是我們需要設定一個值來表示從1到i選不到容積為j的情況這里用-1來表示

? ? ? ? 那么對于第i個位置同樣有兩種情況

? ? ? ? 2,1 當我們不拿第i個物品時價值為dp[i-1][j](這里已經將選不到容積為j的情況包括)

? ? ? ? 2.2 當我們如果要拿第i個物品時，那么我們首先當然是先判斷空間j夠不夠，然后還要判斷

dp[i-1][j-v[i]]這個位置是否有意義即是否為-1，如果有意義那么

? ? ? ??dp[i][j] = max(dp[i-1][j-v[i]]+w[i],dp[i][j])

? ? ? ? 3.初始化

? ? ? ? 這里當i == 0時如果要選擇容積等于j的最大價值顯然是沒有意義的所以我們將dp[0][j](j>=1&&j<=V)初始化為-1

? ? ? ? 當j == 0時只需要不選擇物品即可所以初始化dp[i][0]（i >= 1&&i<=n）為0

? ? ? ? 4.填表順序同上

 for(int i = 1;i<=V;i++) dp[0][i] = -1;int ret2 = -1;for(int i = 1;i<=n;i++)for(int j = 1;j<=V;j++){dp[i][j] = dp[i-1][j];if(j>=v[i] && (dp[i-1][j-v[i]] != -1))dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]]+w[i]);}for(int i = 1;i<=n;i++) ret2 = max(ret2,dp[i][V]);if(ret2 == -1) cout<<0<<endl;else cout<<ret2<<endl;

下面講講這個算法的優化

????????我們在填表的時候發現只用到了相鄰的兩行其實這里可以用滾動數組來優化，只需要一個dp[N]即可當我們填表時只需要在原表操作，但是我們的填表順序變為了從右往左因為在填dp[i][j]時我們用到了dp[i-1][j]和dp[i-1][j-v[i]]顯然dp[i-1][j-v[i]]位置在dp[i-1][j]前面所以如果從左往右填表會導致在填后一個位置的時候前面的位置的值已經被更新

#include<iostream>using namespace std;const int N = 1010;int n,V,v[N],w[N];
int dp[N];int main()
{int ret1 = 0;cin>>n>>V;for(int i = 1;i<=n;i++) cin>>v[i]>>w[i];for(int i = 1;i<=n;i++)for(int j = V;j>=v[i];j--){dp[j] = max(dp[j],dp[j-v[i]]+w[i]);ret1 = max(ret1,dp[j]);}cout<<ret1<<endl;//第二問的初始化for(int i = 1;i<=V;i++) dp[i] = -1;int ret2 = -1;for(int i = 1;i<=n;i++)for(int j = V;j>=v[i];j--){if((dp[j-v[i]] != -1))dp[j] = max(dp[j],dp[j-v[i]]+w[i]);}for(int i = 1;i<=n;i++) ret2 = max(ret2,dp[V]);if(ret2 == -1) cout<<0<<endl;else cout<<ret2<<endl;return 0;
}