前言
對0-1背包問題的二維dp數(shù)組以及一維dp數(shù)組的思路分析
來源：代碼隨想錄 link
本文是我對01背包問題的理解，在本文中具體分析dp數(shù)組的形成過程，最核心的地方就是我對每種情況下的01背包問題給出了代碼運(yùn)行結(jié)果，便于讀者理解。
重點(diǎn)解釋了為什么一維dp數(shù)組的01背包問題為什么要倒敘遍歷背包，以及為什么不能先遍歷背包，只能先遍歷物品。
1，一維dp數(shù)組為什么不能正序遍歷書包？
因為正序遍歷背包會導(dǎo)致同一個物品被放了兩次，但是01背包要求同一物品只能被放一次。文章來源：http://www.zghlxwxcb.cn/news/detail-775217.html
2，一維dp數(shù)組為什么不能先遍歷背包？
因為能用一維dp數(shù)組解決01背包問題的原理就是先遍歷物品時dp數(shù)組是一行一行形成的（具體過程正文中有結(jié)果顯示），下一行的數(shù)據(jù)只受到上一行數(shù)據(jù)的影響，因此可以只用一維數(shù)組去解決01背包問題，但是先遍歷書包時dp數(shù)組時一列一列形成的（具體過程正文中有結(jié)果顯示），這二者本質(zhì)上就是相悖的，如果要強(qiáng)行理解的話，就是如果先遍歷背包時，只會往背包中放入一件物品（正文中有具體結(jié)果演示）。文章來源地址http://www.zghlxwxcb.cn/news/detail-775217.html
一、0-1背包問題
有n件物品和一個最多能背重量為w 的背包。第i件物品的重量是weight[i]，得到的價值是value[i] 。每件物品只能用一次，求解將哪些物品裝入背包里物品價值總和最大
舉例說明：假設(shè)背包最大重量為4，物品的重量以及價值如表所示：
| 重量weight | 價值value | |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
下面分別通過二維db數(shù)組以及一維dp數(shù)組進(jìn)行分析。
二、二維dp數(shù)組01背包問題代碼詳解
1.遞推關(guān)系式
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
dp[i][j]：從物品0到物品i中任意取，放入容量為j的背包，可放入物品的最大價值為dp[i][j]。
遞推關(guān)系式的含義為：01背包問題可以分解為不放物品i和放物品i
即dp[i][j]為放物品i和不放物品i的得到的價值的最大值。
2.代碼詳解
2.1先遍歷物品
根據(jù)代碼隨想錄的介紹，二維dp數(shù)組的01背包問題先遍歷物品還是先遍歷背包均可。
如果先遍歷物品，代碼如下：
其中為了看到每次遍歷后dp數(shù)組的變化，我將其打印輸出，以便分析。
#include<iostream>
#include<vector>
#include <iomanip>
using namespace std;
//打印dp數(shù)組
void print_dparr(vector<vector<int>>& dp)
{
int row = dp.size();
int col = dp[0].size();
for (int i = 0;i < row;i++)
{
for (int j = 0;j < col;j++)
{
cout <<std::left << setw(2) << dp[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
void test_2_wei_bag_problem1() {
vector<int> weight = { 1, 3, 4 };
vector<int> value = { 15, 20, 30 };
int bagweight = 4;
// 二維數(shù)組
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
// 初始化
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
cout << "從物品0中取物品" << endl;
print_dparr(dp);
// weight數(shù)組的大小 就是物品個數(shù)
for (int i = 1; i < weight.size(); i++) { // 遍歷物品
for (int j = 0; j <= bagweight; 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]] + value[i]);
}
cout << "從物品0"<<"到物品"<<i << "中取物品" << endl;
print_dparr(dp);
}
cout <<"最終結(jié)果為:"<< dp[weight.size() - 1][bagweight] << endl;
}
int main() {
test_2_wei_bag_problem1();
return 0;
}
代碼運(yùn)行結(jié)果如下：
dp數(shù)組形成過程
先遍歷物品時，整個dp矩陣的下一行數(shù)據(jù)由上一行數(shù)據(jù)計算得到，
這也為使用一維dp數(shù)組解決01背包問題埋下伏筆。
2.2.先遍歷背包
同理先遍歷背包再遍歷物品可以得到相同結(jié)果，但是此時由于遍歷順序的改變，dp數(shù)組的形成過程發(fā)生了變化，首先附上代碼：
#include<iostream>
#include<vector>
#include <iomanip>
using namespace std;
//打印dp數(shù)組
void print_dparr(vector<vector<int>>& dp)
{
int row = dp.size();
int col = dp[0].size();
for (int i = 0;i < row;i++)
{
for (int j = 0;j < col;j++)
{
cout <<std::left << setw(2) << dp[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
void test_2_wei_bag_problem1() {
vector<int> weight = { 1, 3, 4 };
vector<int> value = { 15, 20, 30 };
int bagweight = 4;
// 二維數(shù)組
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
// 初始化
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
// weight數(shù)組的大小 就是物品個數(shù)
// 遍歷物品
int i;
for (int j = 0; j <= bagweight; j++) { // 遍歷背包容量
for ( i = 1; 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]] + value[i]);
}
cout << "從物品0到物品2中取物品放到容量為"<<j<<"的背包" << endl;
print_dparr(dp);
}
cout <<"最終結(jié)果為:"<< dp[weight.size() - 1][bagweight] << endl;
}
int main() {
test_2_wei_bag_problem1();
return 0;
}
代碼運(yùn)行結(jié)果如下：
dp數(shù)組形成過程
dp數(shù)組形成過程分析
由不同的遍歷順序的運(yùn)行結(jié)果可知，先便利物品時dp數(shù)組是一行一行形成的，而先遍歷背包時，dp數(shù)組是一列一列形成的。
如果先遍歷物品，則其思想為從物品0到物品i中選物品放入容量為4的背包中得到的最大價值，其中i由0取到2。
如果先遍歷背包，則其思想為從物品0到物品2中選物品放到容量為j的背包中得到的最大價值，其中j由0取到4。
根據(jù)遞推關(guān)系式可知 dp[i][j] 與 i-1 行的 0 到 j-1 這些數(shù)據(jù)有關(guān)，這個思想對理解一維dp數(shù)組為什么倒序遍歷很有用。
二維dp數(shù)組的01背包問題較好理解，下面介紹一維dp數(shù)組的01背包問題。
三、一維dp數(shù)組01背包問題代碼詳解
1.遞推關(guān)系式
利用滾動數(shù)組的形式將二維數(shù)組降為一維數(shù)組，目前考慮先遍歷物品的情況，后續(xù)分析先遍歷背包的情況。
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
可以寫成一維形式的原因在上述二維dp數(shù)組中其實已經(jīng)略微闡述了一下，現(xiàn)在進(jìn)行詳細(xì)分析。
在上述分析中，我們知道dp[i][j] 只與 i-1 行的 0 到 j-1 這些數(shù)據(jù)有關(guān)，即dp矩陣的下一行數(shù)據(jù)只與上一行的一些數(shù)據(jù)有關(guān)，因此完全可以利用一維數(shù)組重復(fù)使用。
此時dp[j]的含義為：容量為j的背包可以背的最大價值。
2.代碼詳解
背包倒序遍歷
下面分析一下先遍歷物品時的一維dp數(shù)組解決01背包問題的代碼，注意此時是倒序遍歷背包：
#include<iostream>
#include<vector>
#include <iomanip>
using namespace std;
void print_dparr(vector<int>& dp)
{
int col = dp.size();
for (int j = 0;j < col;j++)
{
cout << std::left << setw(2) << dp[j] << " ";
}
cout << endl;
cout << endl;
}
void test_1_wei_bag_problem() {
vector<int> weight = { 1, 3, 4 };
vector<int> value = { 15, 20, 30 };
int bagWeight = 4;
// 初始化
vector<int> dp(bagWeight + 1, 0);
for (int i = 0; i < weight.size(); i++) { // 遍歷物品
for (int j = bagWeight; j >= weight[i]; j--) { // 遍歷背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
cout << "從物品0到物品" << i << "取物品放到背包中" << endl;
print_dparr(dp);
}
cout <<"最終結(jié)果為："<< dp[bagWeight] << endl;
}
int main() {
test_1_wei_bag_problem();
return 0;
}
運(yùn)行結(jié)果為：
可以看到dp數(shù)組的形成過程與二維dp數(shù)組的形成過程一致，只不過此時的dp數(shù)組是一維的，把三個一維dp數(shù)組拼在一起便形成了二維dp數(shù)組的形式。
背包正序遍歷
在一維dp數(shù)組求解01背包問題中很重要的一點(diǎn)就是書包的遍歷順序，此時書包的遍歷順序只能是倒序遍歷，具體原因如下：
首先先將代碼改成正序遍歷的形式，具體代碼在此不再贅述，只需要把上述代碼的循環(huán)改成如下形式：
for (int i = 0; i < weight.size(); i++) { // 遍歷物品
for (int j = 0; j <= bagWeight; j++) {// 遍歷背包容量
if (j < weight[i]) continue;
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
cout << "從物品0到物品" << i << "取物品放到背包中" << endl;
print_dparr(dp);
}
代碼運(yùn)行結(jié)果如下：
可以發(fā)現(xiàn)結(jié)果不一樣了，我們只看第一組數(shù)據(jù)來分析一下產(chǎn)生這種現(xiàn)象的原因，即從物品0中取物品放到背包中得到的結(jié)果為
正序遍歷的結(jié)果：
0 15 30 45 60
倒序遍歷的結(jié)果：
0 15 15 15 15
對比二者可以很容易發(fā)現(xiàn)以下現(xiàn)象：
30=15+15
45=30+15
60=45+15
從遞推關(guān)系式出發(fā)：
初始化時dp[0] dp[1] dp[2]均為0,weight[0]=1,value[0]=15。
正序遍歷的結(jié)果
dp[1] = dp[1 - weight[0]] + value[0] = dp[0] + 15 = 15
dp[2] = dp[2 - weight[0]] + value[0] = dp[1] + 15 = 30
倒序遍歷的結(jié)果
dp[2] = dp[2 - weight[0]] + value[0] = dp[1] + 15 = 15
dp[1] = dp[1 - weight[0]] + value[0] = dp[0] + 15 = 15
下面這段話是理解一維dp數(shù)組的核心之處
可以發(fā)現(xiàn)正序遍歷時計算 dp[2] 時把 dp[1]=15 加上去了，意味著物品0被放入了兩次，但實際上加的應(yīng)該是dp[1]=0 。換種方式理解就是dp[2]的正確計算方式應(yīng)該是上一行的dp[1]加上15，而如果正序遍歷的話，便使得dp[1]的值發(fā)生了改變，此時計算的是本行的dp[1]加上15。
因此需要倒序遍歷使得每次取得狀態(tài)不會和之前取得狀態(tài)重合，這樣每種物品就只取一次了。
3.先遍歷背包
上述代碼及分析均基于先遍歷物品，現(xiàn)在分析先遍歷背包時的情況。首先從上述分析中我們可以知道，先遍歷背包時，二維dp數(shù)組是一列一列形成的，但是此時我們用一維dp數(shù)組時，我們只能按行形成dp數(shù)組，所以只能先遍歷物品。
如果非要先遍歷背包，可以將上述代碼中的循環(huán)代碼寫成如下形式：
for (int j = bagWeight; j >= 0; j--) {
for (int i = 0; i < weight.size(); i++) { // 遍歷物品
if (j < weight[i]) continue;
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
cout << "背包容量為" << j << "時的結(jié)果" << endl;
print_dparr(dp);
}
運(yùn)行結(jié)果如下：
首先結(jié)果是錯誤的，這是由于先遍歷背包時我們每次只往背包中放入一件物品，所以在背包容量為4時的結(jié)果為：
0 0 0 0 30
我們只需要知道先遍歷書包跟一維dp數(shù)組解決01背包問題的原理相悖，因為根據(jù)上述的dp數(shù)組形成過程可以知道，先遍歷書包的二維dp數(shù)組是一列一列往后形成的，而一維dp數(shù)組解決01背包問題的原理是由于dp數(shù)組可以按行去生成，這兩者從本質(zhì)上就是相悖的，沒有討論的必要。
總結(jié)
以上就是我對01背包問題的理解，最核心的地方就是我對每種情況下的01背包問題給出來代碼運(yùn)行結(jié)果，便于讀者理解。
對于二維dp數(shù)組的01背包問題不多贅述，比較好理解。重點(diǎn)在于一維dp數(shù)組的01背包問題為什么要倒序遍歷背包，以及為什么不能先遍歷背包，只能先遍歷物品。
1，一維dp數(shù)組為什么不能正序遍歷書包？
因為正序遍歷背包會導(dǎo)致同一個物品被放了兩次，但是01背包要求同一物品只能被放一次。
2，一維dp數(shù)組為什么不能先遍歷背包？
因為能用一維dp數(shù)組解決01背包問題的原理就是先遍歷物品時dp數(shù)組是一行一行形成的（具體過程正文中有結(jié)果顯示），下一行的數(shù)據(jù)只受到上一行數(shù)據(jù)的影響，因此可以只用一維數(shù)組去解決01背包問題，但是先遍歷書包時dp數(shù)組時一列一列形成的（具體過程正文中有結(jié)果顯示），這二者本質(zhì)上就是相悖的，如果要強(qiáng)行理解的話，就是如果先遍歷背包時，只會往背包中放入一件物品（正文中有具體結(jié)果演示）。
到了這里，關(guān)于0-1背包問題思路分析，重點(diǎn)解釋一維dp數(shù)組的01背包問題為什么要倒序遍歷背包，以及為什么不能先遍歷背包，只能先遍歷物品的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
