前言：本文詳細(xì)梳理了背包問(wèn)題原理硅则，LeetCode實(shí)戰(zhàn)請(qǐng)見(jiàn)背包問(wèn)題原理及LeetCode實(shí)戰(zhàn)（下）。

零噪裕、概述

背包問(wèn)題及其變形在筆試蹲盘、面試中經(jīng)常出現(xiàn)，欲解決此類問(wèn)題膳音，需要明確三種典型的基本背包問(wèn)題召衔，掌握其原理和代碼邏輯，并通過(guò)LeetCode實(shí)戰(zhàn)開拓思維祭陷。本文介紹了0-1背包問(wèn)題苍凛、完全背包問(wèn)題趣席、多重背包問(wèn)題以及幾道LeetCode典型例題來(lái)拓展背包問(wèn)題的使用場(chǎng)景，旨在讓讀者由淺入深地理解背包問(wèn)題毫深。
背包問(wèn)題一般使用動(dòng)態(tài)規(guī)劃的思想來(lái)解答吩坝，典型的三種背包問(wèn)題都可以使用二維動(dòng)態(tài)規(guī)劃來(lái)解決，能滿足一般筆試的要求哑蔫。在理解好二維動(dòng)態(tài)規(guī)劃的基礎(chǔ)上钉寝，要掌握一維動(dòng)態(tài)規(guī)劃數(shù)組的邏輯與寫法，這種方法在時(shí)間闸迷、空間復(fù)雜度上均優(yōu)于二維的動(dòng)態(tài)規(guī)劃嵌纲，在代碼的處理上也比較簡(jiǎn)單。
動(dòng)態(tài)規(guī)劃的核心是找到邊界（初始化）和狀態(tài)轉(zhuǎn)移方程腥沽，文章會(huì)從思路和代碼兩個(gè)層面來(lái)介紹逮走。

一、0-1背包問(wèn)題

1.1 問(wèn)題描述：

有一個(gè)容量為 C 的背包今阳，和一些物品师溅。這些物品分別有兩個(gè)屬性，體積 w 和價(jià)值 v盾舌，每種物品的數(shù)量只有一個(gè)墓臭。要求用這個(gè)背包裝下價(jià)值盡可能多的物品，求該最大價(jià)值妖谴，背包可以不被裝滿窿锉。

1.2 邏輯與思路：

先思考大問(wèn)題的子問(wèn)題，如果對(duì)所有物品進(jìn)行遍歷膝舅，對(duì)每一件物品來(lái)說(shuō)嗡载，只有選擇和不選擇兩種情況，我們需要找到使最終結(jié)果最優(yōu)的方案仍稀。
定義F[i][j]為前i+1個(gè)物品中洼滚，當(dāng)最大背包容量為j時(shí)，背包能裝載的最大價(jià)值技潘。例如遥巴，F[0][3]表示只考慮第一個(gè)物品，如果背包的最大容量為3崭篡，那么能裝的價(jià)值是多少，F[2][4]表示只考慮前三個(gè)物品吧秕，如果背包的最大容量為4琉闪，那么能裝的價(jià)值是多少。這樣以來(lái)砸彬，我們最終要的結(jié)果就是F[n-1][C]颠毙，其中n為物品的個(gè)數(shù)斯入。
從i=0的情況開始考慮，F[0][j]表示的是只考慮第一件物品蛀蜜，背包容量為j時(shí)能裝載的最大價(jià)值刻两。顯然，當(dāng)j>=w[0]時(shí)滴某，F[0][j]=v[0]磅摹，反之，F[0][j]=0霎奢。這就是動(dòng)態(tài)規(guī)劃的邊界户誓。
如果i>0呢？對(duì)于第i件物品幕侠，有裝和不裝兩種選擇帝美。不裝的話很簡(jiǎn)單，當(dāng)前的F[i][j]就等于F[i-1][j]晤硕。如果裝載上第i件物品的話悼潭，那么背包中就有w[i]的重量是屬于這件物品的，其余的物品最多只能占用那剩余的j-w[i]的空間舞箍，所以舰褪，F[i][j]等于前i-1件物品占用j-w[i]空間的最大價(jià)值即F[i-1][j-w[i]]與當(dāng)前物品價(jià)值v[i]之和。所以就得到了狀態(tài)轉(zhuǎn)移方程為：F[i][j]=max(F[i-1][j], F[i-1][j-w[i]]+v[i])创译。
如果前面的推導(dǎo)你似懂非懂抵知，那么來(lái)看下面這個(gè)具體的例子：
假設(shè)物品的體積w[i]=[5,6,2,3,4]，物品的價(jià)值v[i]=[6,12,5,6,6]软族，背包容量C=10刷喜。那么可得F[i][j]的表格為：

這張表格是從第一行開始由左向右一行一行建立的。i=0的行是初始化的結(jié)果立砸，當(dāng)j>=w[0]即j>=5時(shí)掖疮，F[0][j]=v[0]=6。從i=1開始颗祝，F[i][j]就取決于上一行的結(jié)果了浊闪，也就是取決于F[i-1][j]（正上方的格子）和F[i-1][j-w[i]]（上一行的左側(cè)）這兩個(gè)位置的數(shù)字。

1.3 代碼實(shí)現(xiàn)

首先螺戳，main()函數(shù)中給定了條件搁宾，包括物品的重量、價(jià)值倔幼，和背包容量(后面的代碼都是使用的這個(gè)main()函數(shù)）盖腿。

int main()
{
    int weight[]={5,6,2,3,4},value[]={6,12,5,6,6};
    vector<int> w(weight,weight+5),v(value,value+5);
    int C = 10;
    bag_0_1(w,v,C);
}

函數(shù)的實(shí)現(xiàn)也比較簡(jiǎn)單，先對(duì)F[i][j]初始化第一行，然后根據(jù)遍歷物品翩腐，根據(jù)狀態(tài)轉(zhuǎn)移函數(shù)計(jì)算鸟款。

int bag_0_1(vector<int> &w, vector<int> &v, int C)
{
    int len=w.size();
    vector<vector<int> > F(len,vector<int>(C+1,0)); // 把F初始化為0，否則有的編譯器通過(guò)不了茂卦；
    // 初始化F的第一行
    for(int j=0;j<=C;j++)
    {
        if(j>=w[0])
            F[0][j]=v[0];
    }
    // F[i][j]的 j 可以理解為當(dāng)前背包最大容量為j;
    for(int i=1;i<len;i++)
    {
        for(int j=1;j<=C;j++)
        {
            if(j>=w[i])
                F[i][j]=max(F[i-1][j],F[i-1][j-w[i]]+v[i]);
            else
                F[i][j]=F[i-1][j];
            
        }
    }
    return F[len-1][C];
}

1.4 解法優(yōu)化

在這個(gè)問(wèn)題的處理中何什，尤其是通過(guò)前面的表格更容易發(fā)現(xiàn)，第i行的計(jì)算完全依賴于第i-1行的結(jié)果等龙，與更前面的行沒(méi)有任何關(guān)系处渣。所以從這個(gè)角度，二維的數(shù)組完全可以用一維數(shù)組來(lái)替代而咆。一維數(shù)組的內(nèi)容隨著外層迭代的進(jìn)行而不斷更新霍比。
根據(jù)前面的表格來(lái)理解這個(gè)過(guò)程：已經(jīng)計(jì)算出了第i-1行的數(shù)據(jù)，下一次迭代的過(guò)程其實(shí)就是對(duì)這C+1個(gè)數(shù)據(jù)依次更新的過(guò)程暴备。這里要注意一點(diǎn)細(xì)節(jié)悠瞬，就是更新的第j個(gè)數(shù)據(jù)取決于原有的這個(gè)位置上的數(shù)據(jù)和j-w[i]這個(gè)位置上的數(shù)據(jù)，我們要保證j-w[i]這個(gè)位置（在位置j的前面）不要被更新掉涯捻。所以這里的內(nèi)層循環(huán)要選擇逆序循環(huán)浅妆。

int bag_0_1_opt(vector<int> &w, vector<int> &v, int C)
{
    int len=w.size();
    vector<int> F(C+1,0);
    for(int i=0;i<len;i++)
    {
        // j要逆序遍歷，否則更新后的F[j]會(huì)影響后續(xù)計(jì)算
        for(int j=C;j>=w[i];j--)
        {
            F[j]=max(F[j],F[j-w[i]]+v[i]);
        }
    }
    return F[C];
}

優(yōu)化后的算法主要減小了空間復(fù)雜度障癌。

二凌外、完全背包問(wèn)題

2.1 問(wèn)題描述

有一個(gè)容量為 C 的背包，和一些物品涛浙。這些物品分別有兩個(gè)屬性康辑，體積 w 和價(jià)值 v，每種物品的數(shù)量都有無(wú)限個(gè)轿亮。要求用這個(gè)背包裝下價(jià)值盡可能多的物品疮薇，求該最大價(jià)值，背包可以不被裝滿我注。

2.2 邏輯與思路

完全背包問(wèn)題和0-1背包問(wèn)題的不同點(diǎn)在于前者的物品可以選任意個(gè)按咒，而后者物品個(gè)數(shù)只有一個(gè)。不同于0-1背包中物品具有的兩種選擇（放或不放）但骨，完全背包問(wèn)題對(duì)每個(gè)物品的選擇為不放或放n個(gè)励七。可以看到奔缠，完全背包問(wèn)題與0-1背包問(wèn)題的相同點(diǎn)眾多掠抬，處理的思路也應(yīng)該類似。那么如何處理“放n個(gè)”問(wèn)題校哎，n該怎樣定義两波？
依舊定義F[i][j]為前i+1個(gè)物品中，當(dāng)最大背包容量為j時(shí)，背包能裝載的最大價(jià)值雨女。首先確定動(dòng)態(tài)規(guī)劃的邊界，當(dāng)i=0時(shí)阳准，F[0][j]表示只考慮第一件物品氛堕，容量為j的背包中能裝載的最大價(jià)值。因?yàn)楸嘲悄苎b一件物品野蝇，那么當(dāng)然要盡可能多地裝讼稚，所以F[0][j]=(j/w[0])*v[0]。
邊界問(wèn)題確定了绕沈，下面處理“不放或放n個(gè)”的問(wèn)題锐想。對(duì)于i>0的情況，同樣地乍狐，如果選擇不放第i件物品赠摇，那么此時(shí)的F[i][j]=F[i-1][j]。假如要在背包中放置k個(gè)物品i浅蚪，那么其余的物品最多只能占用j-k*w[i]的空間藕帜。其中k的取值要滿足j-k*w[i]>=0。所以狀態(tài)轉(zhuǎn)移方程為F[i][j]=max(F[i-1][j], F[i-1][j-k*w[i]]+k*v[i])惜傲，其中洽故，j-k*w[i]>=0。

2.3 代碼實(shí)現(xiàn)

在邏輯上盗誊，完全背包問(wèn)題與0-1背包問(wèn)題相同时甚，差別主要是在初始化和轉(zhuǎn)移方程的細(xì)節(jié)，具體代碼如下：

int bag_com(vector<int> &w, vector<int> &v, int C)
{
    int len=w.size();
    vector<vector<int> > F(len,vector<int>(C+1,0));
    // 確定動(dòng)態(tài)規(guī)劃的邊界哈踱，初始化
    for(int j=0;j<=C;j++)
        F[0][j]=(j/w[0])*v[0];
    for (int i = 1; i < len; i++)
    {
        for (int j = w[i]; j <= C; j++)
        {    
            //狀態(tài)轉(zhuǎn)移方程的處理
            int k=j/w[i];
            F[i][j]=F[i-1][j];
            while(k)
            {
                F[i][j]=max(F[i][j],F[i-1][j-k*w[i]]+k*v[i]);
                k--;
            }  
        }
    }
    return F[len-1][C];
}

2.4 解法優(yōu)化

在完全背包問(wèn)題中荒适，尤其是通過(guò)狀態(tài)轉(zhuǎn)移方程可以看出，第i行的數(shù)據(jù)僅依賴于前一行的數(shù)據(jù)嚣鄙，所以此問(wèn)題依然可以使用一維數(shù)組來(lái)解決吻贿。
這里有一點(diǎn)特別值得注意，在0-1背包問(wèn)題的解法優(yōu)化中提到的“逆序循環(huán)”是為了防止舊位置上的結(jié)果被更新掉哑子，而在完全背包問(wèn)題則不然舅列，因?yàn)榕f位置上的結(jié)果可以被更新！可以這樣理解：在第i次遍歷中卧蜓，如果第j個(gè)位置被更新了帐要，也就代表那個(gè)位置的最優(yōu)結(jié)果是包含若干個(gè)物品i的，后續(xù)再用到那個(gè)位置的話弥奸，也是在已經(jīng)包含若干個(gè)物品i的結(jié)果中榨惠，再加若干個(gè)物品i，這是符合題意的。所以內(nèi)層循環(huán)采用的是順序循環(huán)赠橙。
代碼如下：

int bag_com_opt(vector<int> &w, vector<int> &v, int C)
{
    int len=w.size();
    vector<int> F(C+1,0);
    for (int i = 0; i < len; i++)
        for(int j=w[i];j<=C;j++)
        {
            F[j]=max(F[j],F[j-w[i]]+v[i]);
        }
    return F[C];
}

三耽装、多重背包問(wèn)題

多重背包問(wèn)題在完全背包問(wèn)題的基礎(chǔ)上做了一點(diǎn)限制，即限制了每種物品最多可用的件數(shù)期揪。0-1背包的求解方法已經(jīng)學(xué)會(huì)了掉奄，現(xiàn)在把復(fù)雜問(wèn)題簡(jiǎn)單化，對(duì)于可用物品件數(shù)為n的物品凤薛，我們把這n件物品視為不同的物品來(lái)擴(kuò)展w[i]和v[i]姓建，這樣就把這類問(wèn)題轉(zhuǎn)化成了0-1背包問(wèn)題，即可按前面的解法去解決缤苫。