01背包問題
由于leetcode上沒原題，故參考卡哥意見自己編題記錄一下。

創新互聯公司成都網站建設按需定制，是成都網站維護公司,為門窗定制提供網站建設服務,有成熟的網站定制合作流程，提供網站定制設計服務：原型圖制作、網站創意設計、前端HTML5制作、后臺程序開發等。成都網站設計熱線：18982081108一、題干

背包大重量為4。物品為：

物品名稱	重量	價值
0	1	15
1	3	20
2	4	30
–	–	–

問背包能背的物品大價值是多少？

二、解法

二維dp：
遞推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

void test_2_wei_bag_problem1() {vectorweight = {1, 3, 4};
    vectorvalue = {15, 20, 30};
    int bagweight = 4;

    // 二維數組
    vector>dp(weight.size(), vector(bagweight + 1, 0));

    // 初始化
    for (int j = weight[0]; j<= bagweight; j++) {dp[0][j] = value[0];
    }

    // weight數組的大小 就是物品個數
    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<< dp[weight.size() - 1][bagweight]<< endl;
}

int main() {test_2_wei_bag_problem1();
}

一維dp：
遞推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

void test_1_wei_bag_problem() {vectorweight = {1, 3, 4};
    vectorvalue = {15, 20, 30};
    int bagWeight = 4;

    // 初始化
    vectordp(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<< dp[bagWeight]<< endl;
}

int main() {test_1_wei_bag_problem();
}

三、問答題

1. 為什么二維dp兩個for循環的嵌套順序這么寫？反過來寫行不行？
   答：反過來可以，原因是遞推公式里本層遍歷輸入都在本層的左上角。

2. 講一講初始化的邏輯。
   答：二維背包中，dp[i][0]，無論是選取哪些物品，背包價值總和一定為0；而dp[0][i], 當 i >= weight[0] 時 = value[0]，否則為0; 其他無所謂，都會被覆蓋。
   一維背包中，dp[0] = 0, 如果如果題目給的價值都是正整數那么非0下標都初始化為0就可以了，如果題目給的價值有負數，那么非0下標就要初始化為負無窮。這樣才能讓dp數組在遞歸公式的過程中取的大的價值，而不是被初始值覆蓋了。

3. 一維數組的01背包，兩個for循環的順序反過來寫行不行？為什么？
   答：不可以。因為一維dp的寫法，背包容量一定是要倒序遍歷（倒序遍歷是為了保證物品i只被放入一次！），如果遍歷背包容量放在上一層，那么每個dp[j]就只會放入一個物品，即：背包里只放入了一個物品。（原因是，dp數組初始化是0，在先遍歷背包容量時，由于從后向前遍歷，dp[j - weight[i]] = 0, 沒用上上一個狀態。）

倒序遍歷的原因是，本質上還是一個對二維數組的遍歷，并且右下角的值依賴上一層左上角的值，因此需要保證左邊的值仍然是上一層的，從右向左覆蓋。

Leetcode 416. 分割等和子集

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

文章標題：代碼隨想錄算法訓練營第42天|01背包問題416.分割等和子集-創新互聯
本文URL：http://vcdvsql.cn/article36/epdsg.html

成都網站建設公司_創新互聯，為您提供企業網站制作、虛擬主機、網站維護、App開發、關鍵詞優化、企業建站

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯