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

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

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

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

問背包能背的物品大價(jià)值是多少？

二、解法

二維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ù)組的大小 就是物品個(gè)數(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兩個(gè)for循環(huán)的嵌套順序這么寫？反過來寫行不行？
   答：反過來可以，原因是遞推公式里本層遍歷輸入都在本層的左上角。

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

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

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

Leetcode 416. 分割等和子集

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

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

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

廣告

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