沒(méi)想到，背包問(wèn)題解題也有套路

一、概述

背包問(wèn)題是一類比較特殊的動(dòng)態(tài)規(guī)劃問(wèn)題，這篇文章的側(cè)重點(diǎn)會(huì)在答案的推導(dǎo)過(guò)程上，我們還是會(huì)使用之前提到的解動(dòng)態(tài)規(guī)劃問(wèn)題的四個(gè)步驟來(lái)思考這類問(wèn)題。

在講述背包問(wèn)題之前，首先提及一下，背包類動(dòng)態(tài)規(guī)劃問(wèn)題和其他的動(dòng)態(tài)規(guī)劃問(wèn)題的不同之處在于，背包類動(dòng)態(tài)規(guī)劃問(wèn)題會(huì)選用值來(lái)作為動(dòng)態(tài)規(guī)劃的狀態(tài)，你可以回顧下之前我們討論過(guò)的動(dòng)態(tài)規(guī)劃問(wèn)題，基本上都是利用數(shù)組或者是字符串的下標(biāo)來(lái)表示動(dòng)態(tài)規(guī)劃的狀態(tài)。

針對(duì)背包類問(wèn)題，我們依然可以畫(huà)表格來(lái)輔助我們思考問(wèn)題，但是背包類問(wèn)題有基本的雛形，題目特征特別明顯，當(dāng)你理解了這類問(wèn)題的解法后，遇到類似問(wèn)題基本上不需要額外的輔助就可以給出大致的解法，這也就是說(shuō)，學(xué)習(xí)背包類問(wèn)題是一個(gè)性價(jià)比很高的事情，理解了一個(gè)特定問(wèn)題的解法，基本上一類問(wèn)題都可以直接套這個(gè)解法。

二、問(wèn)題雛形

首先我們來(lái)看看這樣一個(gè)問(wèn)題：

有 N 件物品和一個(gè)容量為 V 的背包。第 i 件物品的體積是 C[i]，價(jià)值是 W[i]。求解將哪些物品裝入背包可使價(jià)值總和最大。求出最大總價(jià)值

話不多說(shuō)，我們還是按之前的分析四步驟來(lái)看看這個(gè)問(wèn)題：

問(wèn)題拆解

我們要求解的問(wèn)題是 “背包能裝入物品的最大價(jià)值”，這個(gè)問(wèn)題的結(jié)果受到兩個(gè)因素的影響，就是背包的大小，以及物品的屬性（包括大小和價(jià)值）。對(duì)于物品來(lái)說(shuō)，只有兩種結(jié)果，放入背包以及不放入背包，這里我們用一個(gè)例子來(lái)畫(huà)畫(huà)表格：

假設(shè)背包的大小是 10，有 4 個(gè)物品，體積分別是 [2,3,5,7]，價(jià)值分別是 [2,5,2,5]。

1、如果我們僅考慮將前一個(gè)物品放入背包，只要背包體積大于 2，此時(shí)都可以獲得價(jià)值為 2 的最大價(jià)值：

圖一

2、如果我們僅考慮將前兩個(gè)物品放入背包，如果背包體積大于或等于 5，表示兩個(gè)物體都可放入，此時(shí)都可以獲得價(jià)值為 2+5=7 的最大價(jià)值，如果不能全都放入，那就要選擇體積不超，價(jià)值最大的那個(gè)：

圖二

3、如果我們僅考慮將前三個(gè)物品放入背包，如果背包體積大于或等于 10，表示三個(gè)物體都可放入，此時(shí)都可以獲得價(jià)值為 2+5+2=9 的最大價(jià)值，如果不能全都放入，那就要選擇體積不超，價(jià)值最大的那個(gè)方案：

圖三

4、如果我們考慮將所有物品放入背包，我們可以依據(jù)前三個(gè)物品放入的結(jié)果來(lái)制定方案：

圖四

這樣，我們就根據(jù)物品和體積將問(wèn)題拆分成子問(wèn)題，也就是 “前 n 個(gè)物品在體積 V 處的最大價(jià)值” 可以由 “前 n - 1 個(gè)物品的情況” 推導(dǎo)得到。

狀態(tài)定義

在問(wèn)題拆解中，我們得知問(wèn)題其實(shí)和背包的體積還有當(dāng)前考慮的物品有關(guān)，因此我們可以定義dp[i][j]表示 “考慮將前 i 個(gè)物品放入體積為 j 的背包里所獲得的最大價(jià)值”

遞推方程

當(dāng)我們考慮是否將第 i 個(gè)物品放入背包的時(shí)候，這里有兩種情況

不放入，也就是不考慮第 i 個(gè)物品，那么問(wèn)題就直接變成了上一個(gè)子問(wèn)題，也就是考慮將 i - 1 個(gè)物品放入背包中，這樣當(dāng)前問(wèn)題的解就是之前問(wèn)題的解：

dp[i][j]=dp[i-1][j]

如果背包體積大于第 i 個(gè)物品的體積，我們可以考慮將第 i 個(gè)物品放入，這個(gè)時(shí)候我們要和之前的狀態(tài)做一個(gè)比較，選取最大的方案：

dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-C[i]]+W[i])

實(shí)現(xiàn)

實(shí)現(xiàn)這一環(huán)節(jié)還是主要考慮狀態(tài)數(shù)組如何初始化，你可以看到，我們每次都要考慮 i - 1，另外還要考慮背包體積為 0 的情況，因此初始化數(shù)組時(shí)多開(kāi)一格可以省去不必要的麻煩

publicintzeroOnePack(intV,int[]C,int[]W){ //防止無(wú)效輸入 if((V<=?0)?||?(C.length?!=?W.length))?{ ????????return?0; ????} ????int?n?=?C.length; ????//?dp[i][j]:?對(duì)于下標(biāo)為?0～i?的物品，背包容量為?j?時(shí)的最大價(jià)值 ????int[][]?dp?=?new?int[n?+?1][V?+?1]; ????//?背包空的情況下，價(jià)值為?0 ????dp[0][0]?=?0; ????for?(int?i?=?1;?i?<=?n;?++i)?{ ????????for?(int?j?=?1;?j?<=?V;?++j)?{ ????????????//?不選物品?i?的話，當(dāng)前價(jià)值就是取到前一個(gè)物品的最大價(jià)值，也就是?dp[i?-?1][j] ????????????dp[i][j]?=?dp[i?-?1][j]; ????????????//?如果選擇物品?i?使得當(dāng)前價(jià)值相對(duì)不選更大，那就選取?i，更新當(dāng)前最大價(jià)值 ????????????if?((j?>=C[i-1])&&(dp[i][j]

這里還有一個(gè)空間上面的優(yōu)化，如果你回到我們之前畫(huà)的表格，考慮前 i 個(gè)問(wèn)題的狀態(tài)只會(huì)依賴于前 i - 1 個(gè)問(wèn)題的狀態(tài)，也就是dp[i][...]只會(huì)依賴于dp[i - 1][...]，另外一點(diǎn)就是當(dāng)前考慮的背包體積只會(huì)用到比其小的體積。

基于這些信息，我們狀態(tài)數(shù)組的維度可以少開(kāi)一維，但是遍歷的方向上需要從后往前遍歷，從而保證子問(wèn)題需要用到的數(shù)據(jù)不被覆蓋，優(yōu)化版本如下：

publicintzeroOnePackOpt(intV,int[]C,int[]W){ //防止無(wú)效輸入 if((V<=?0)?||?(C.length?!=?W.length))?{ ????????return?0; ????} ????int?n?=?C.length; ????int[]?dp?=?new?int[V?+?1]; ????//?背包空的情況下，價(jià)值為?0 ????dp[0]?=?0; ????for?(int?i?=?0;?i?=C[i];--j){ dp[j]=Math.max(dp[j],dp[j-C[i]]+W[i]); } } returndp[V]; }

這里，因?yàn)槲锲分荒鼙贿x中 1 次，或者被選中 0 次，因此我們稱這種背包問(wèn)題為01 背包問(wèn)題。

還有一類背包問(wèn)題，物品可以被選多次或者 0 次，這類問(wèn)題我們稱為完全背包問(wèn)題，這類背包問(wèn)題和 01 背包問(wèn)題很類似，略微的不同在于，在完全背包問(wèn)題中，狀態(tài)dp[i][j]依賴的是dp[i - 1][j]以及dp[i][k] k < j，你可以看看下面的實(shí)現(xiàn)代碼：

publicintcompletePack(intV,int[]C,int[]W){ //防止無(wú)效輸入 if(V==0||C.length!=W.length){ return0; } intn=C.length; //dp[i][j]:對(duì)于下標(biāo)為0～i的物品，背包容量為j時(shí)的最大價(jià)值 int[][]dp=newint[n+1][V+1]; //背包空的情況下，價(jià)值為0 dp[0][0]=0; for(inti=1;i<=?n;?++i)?{ ????????for?(int?j?=?1;?j?<=?V;?++j)?{ ????????????//?不取該物品 ????????????dp[i][j]?=?dp[i?-?1][j]; ????????????//?取該物品，但是是在考慮過(guò)或者取過(guò)該物品的基礎(chǔ)之上(dp[i][...])取 ????????????//?0-1背包則是在還沒(méi)有考慮過(guò)該物品的基礎(chǔ)之上(dp[i?-?1][...])取 ????????????if?((j?>=C[i-1])&&(dp[i][j-C[i-1]]+W[i-1]>dp[i][j])){ dp[i][j]=dp[i][j-C[i-1]]+W[i-1]; } } } //返回，對(duì)于所有物品（0～N），背包容量為V時(shí)的最大價(jià)值 returndp[n][V]; }

類似的，我們還是可以對(duì)狀態(tài)數(shù)組進(jìn)行空間優(yōu)化，依據(jù)我們之前討論的狀態(tài)之間的依賴關(guān)系，完全背包的空間優(yōu)化我們直接把狀態(tài)數(shù)組少開(kāi)一維即可，遍歷方式都不需要改變：

publicintcompletePackOpt(intV,int[]C,int[]W){ if(V==0||C.length!=W.length){ return0; } intn=C.length; int[]dp=newint[V+1]; for(inti=0;i

下面，我們就根據(jù)這兩類背包問(wèn)題，看看遇到類似的問(wèn)題我們是否可以套用上面我們介紹的解法。

三、相關(guān)題目實(shí)戰(zhàn)

LeetCode 第 416 號(hào)問(wèn)題：分割等和子集。

題目來(lái)源：https://leetcode-cn.com/problems/partition-equal-subset-sum/

題目描述

給定一個(gè)只包含正整數(shù)的非空數(shù)組。是否可以將這個(gè)數(shù)組分割成兩個(gè)子集，使得兩個(gè)子集的元素和相等。

注意:

每個(gè)數(shù)組中的元素不會(huì)超過(guò) 100

數(shù)組的大小不會(huì)超過(guò) 200

示例 1:

輸入:[1,5,11,5] 輸出:true 解釋:數(shù)組可以分割成[1,5,5]和[11].

示例 2:

輸入:[1,2,3,5] 輸出:false 解釋:數(shù)組不能分割成兩個(gè)元素和相等的子集.

題目分析

題目給定一個(gè)數(shù)組，問(wèn)是否可以將數(shù)組拆分成兩份，并且兩份的值相等，這里并不是說(shuō)分成兩個(gè)子數(shù)組，而是分成兩個(gè)子集。

直觀的想法是直接遍歷一遍數(shù)組，這樣我們可以得到數(shù)組中所有元素的和，這個(gè)和必須是偶數(shù)，不然沒(méi)法分，其實(shí)很自然地就可以想到，我們要從數(shù)組中挑出一些元素，使這些元素的和等于原數(shù)組中元素總和的一半，“從數(shù)組中找出一些元素讓它們的和等于一個(gè)固定的值”，這么一個(gè)信息能否讓你想到背包類動(dòng)態(tài)規(guī)劃呢？

如果你能想到這個(gè)地方，再配上我們之前講的01 背包問(wèn)題的解法，那么這道題目就可以直接套解法了，這里我就不具體分析了。

參考代碼

publicbooleancanPartition(int[]nums){ if(nums==null||nums.length==0){ returnfalse; } intsum=0; intn=nums.length; for(inti=0;i=nums[i];--j){ dp[j]|=dp[j-nums[i]]; } } returndp[target]; }

LeetCode 第 322 號(hào)問(wèn)題：零錢兌換。

題目來(lái)源：https://leetcode-cn.com/problems/coin-change

題目描述

給定不同面額的硬幣coins和一個(gè)總金額amount。編寫(xiě)一個(gè)函數(shù)來(lái)計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)。如果沒(méi)有任何一種硬幣組合能組成總金額，返回-1。

示例 1:

輸入:coins=[1,2,5],amount=11 輸出:3 解釋:11=5+5+1

示例 2:

輸入:coins=[2],amount=3 輸出:-1

說(shuō)明:
你可以認(rèn)為每種硬幣的數(shù)量是無(wú)限的。

題目分析

題目給定一個(gè)數(shù)組和一個(gè)整數(shù)，數(shù)組里面的值表示的是每個(gè)硬幣的價(jià)值，整數(shù)表示的是一個(gè)價(jià)值，問(wèn)最少選擇多少個(gè)硬幣能夠組成這個(gè)價(jià)值，硬幣可以重復(fù)選擇。

雖然這里只有一個(gè)輸入數(shù)組，但是我們還是可以看到背包的影子，這里的整數(shù)就可以看作是背包的體積，然后數(shù)組里面的值可以看作是物品的體積，那物品的價(jià)值呢？

在這里，你可以形象地認(rèn)為每個(gè)物品的價(jià)值是 1，最后我們要求的是填滿背包的最小價(jià)值，因?yàn)檫@里物品是可以重復(fù)選擇多次的，因此可以歸類于完全背包問(wèn)題，套用之前的解法就可以解題，唯一要注意的一點(diǎn)是，這里我們不在求最大價(jià)值，而求的是最小價(jià)值，因此我們需要先將狀態(tài)數(shù)組初始化成無(wú)窮大。

參考代碼

publicintcoinChange(int[]coins,intamount){ int[]dp=newint[amount+1]; Arrays.fill(dp,Integer.MAX_VALUE); dp[0]=0; for(inti=0;i

輔助動(dòng)畫(huà)

LeetCode 第 518 號(hào)問(wèn)題：零錢兌換II。

題目來(lái)源：https://leetcode-cn.com/problems/coin-change-2/

題目描述

給定不同面額的硬幣和一個(gè)總金額。寫(xiě)出函數(shù)來(lái)計(jì)算可以湊成總金額的硬幣組合數(shù)。假設(shè)每一種面額的硬幣有無(wú)限個(gè)。

示例 1:

輸入:amount=5,coins=[1,2,5] 輸出:4 解釋:有四種方式可以湊成總金額: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1

示例 2:

輸入:amount=3,coins=[2] 輸出:0 解釋:只用面額2的硬幣不能湊成總金額3。

示例 3:

輸入:amount=10,coins=[10] 輸出:1

注意:

你可以假設(shè)：

0 <= amount (總金額) <= 5000

1 <= coin (硬幣面額) <= 5000

硬幣種類不超過(guò) 500 種

結(jié)果符合 32 位符號(hào)整數(shù)

題目分析

這道題目是上一道題目的變形，題目的輸入參數(shù)還是不變，變的是最后的問(wèn)題，這里需要求的是 “有多少種組合方式能夠填滿背包”，我們還是可以套用完全背包的解法，只是最后求解的東西變了，那我們動(dòng)態(tài)規(guī)劃狀態(tài)數(shù)組中記錄的東西相應(yīng)的改變即可，在這道題中，狀態(tài)數(shù)組中記錄組合成該價(jià)值的方案的個(gè)數(shù)即可。

參考代碼

publicintchange(intamount,int[]coins){ int[]dp=newint[amount+1]; dp[0]=1; for(inti=0;i

K Sum。

題目描述

給定一個(gè)輸入數(shù)組 array，還有兩個(gè)整數(shù) k 和 target，在數(shù)組 array 中找出 k 個(gè)元素，使得這 k 個(gè)元素相加等于 target，問(wèn)有多少種組合方式，輸出組合方式的個(gè)數(shù)。

注：在一種組合方式中，一個(gè)元素不能夠被重復(fù)選擇

題目分析

我們之前講過(guò) Two Sum，也提到過(guò) 3 Sum，還有 4 Sum，那這道題是否可以套用之前的解法呢？

這里有一個(gè)細(xì)節(jié)不知道你是否發(fā)現(xiàn)，就是這道題目?jī)H僅是讓你輸出所有組合方式的個(gè)數(shù)，并沒(méi)有讓你輸出所有的組合方式，這是決定是否使用動(dòng)態(tài)規(guī)劃很重要的一點(diǎn)。

如果沒(méi)有這個(gè) k，我相信你會(huì)很直接地想到使用01 背包問(wèn)題的解法，那我們可以思考一下，基于原來(lái)的解法，如果增加了 k 這個(gè)限制，我們需要額外做些什么事情呢？

因?yàn)?k 會(huì)決定問(wèn)題的狀態(tài)，因此我們的狀態(tài)數(shù)組中也要考慮 k，在考慮將第 k 個(gè)元素放入背包中，我們需要看的是背包中存放 k - 1 個(gè)元素的情況，這么看來(lái)，其實(shí)相比普通的01 背包問(wèn)題，這道題目?jī)H僅是增加了一維狀態(tài)，沒(méi)有其他的變化。

參考代碼

publicintkSum(int[]array,intk,inttarget){ int[][]dp=newint[target+1][k+1]; dp[0][0]=1; for(inti=0;i=array[i];--j){ //和普通01背包問(wèn)題相比，僅僅是多了一層狀態(tài)需要考慮 //這層狀態(tài)記錄的是背包里面元素的個(gè)數(shù) //我們放入第r個(gè)元素的時(shí)候，必須確保背包里面已經(jīng)有r-1個(gè)元素 for(intr=1;r<=?k;?++r)?{ ????????????????dp[j][r]?+=?dp[j?-?array[i]][r?-?1]; ????????????} ????????} ????} ????return?dp[target][k]; }

四、總結(jié)

背包類的動(dòng)態(tài)規(guī)劃問(wèn)題我們就先講到這里，我們介紹了兩類比較基礎(chǔ)的背包問(wèn)題，01 背包問(wèn)題和完全背包問(wèn)題，解這類問(wèn)題有既定的模版和思路可以參照，理解了模版問(wèn)題，也就理解了一類問(wèn)題，算是學(xué)習(xí)性價(jià)比很高的一類動(dòng)態(tài)規(guī)劃問(wèn)題。

往往背包類問(wèn)題可以很好地根據(jù)題目的描述判斷出來(lái)，這類問(wèn)題狀態(tài)的定義也比較特殊，就是用值來(lái)作為動(dòng)態(tài)規(guī)劃的狀態(tài)，我們也用了一些習(xí)題來(lái)練習(xí)了一番，相信你對(duì)背包問(wèn)題有了大致的了解，也對(duì)動(dòng)態(tài)規(guī)劃有了更廣的認(rèn)識(shí)。