代碼隨想錄算法訓練營第42天|01背包問題416.分割等和子集-創(chuàng)新互聯(lián)

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

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

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

物品名稱重量價值
0115
1320
2430
–––

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

二、解法

二維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;

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

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

    // 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<< 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循環(huán)的嵌套順序這么寫？反過來寫行不行？
    答：反過來可以，原因是遞推公式里本層遍歷輸入都在本層的左上角。

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

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

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

Leetcode 416. 分割等和子集

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

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

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供企業(yè)網(wǎng)站制作、虛擬主機、網(wǎng)站維護、App開發(fā)、關鍵詞優(yōu)化、企業(yè)建站

廣告

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

微信小程序開發(fā)