定義
dp[i][j]是從物品0到i中挑選物品，放進容量為j的背包中的最大價值總和。

初始化

int dp[maxn][maxn]; memset(dp, sizeof(dp), -0x3f3f3f3f);for(int j = bag_size; j >= 0; j--) dp[0][j] = dp[0][j-weight[0]] + values[0];

先遍歷物品法

for(int i = 0; i < weight.size(); i++)for(int j = 1; j <= bag_size; j++){if(j < weight[i])dp[i][j] = dp[i-1][j];else dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + values[i]);}

先遍歷物品法

for(int j = 1; j <= bag_size; j++)for(int i = 0; i < weight.size(); i++){if(j < weight[i])dp[i][j] = dp[i-1][j];else dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + values[i]);}

輸出

return dp[weight.size()-1][bag_size];

總結

以上是生活随笔為你收集整理的动态规划 0-1背包问题 二维数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。