大站網(wǎng)站建設(shè)百度自動(dòng)優(yōu)化
目錄
0、背包問題分類
1、?0/1背包簡化版
【代碼】
2、0/ 1背包的方案數(shù)
【思路】
【做法】
【代碼】
空間優(yōu)化1：交替滾動(dòng)
空間優(yōu)化2：自我滾動(dòng)
?3、完全背包
【思路】
【代碼】
4、分組背包?
核心代碼
5、多重背包
多重背包解題思路1:轉(zhuǎn)化為0/1背包
多重背包解題思路2:直接DP
?????????核心代碼
多重背包解題思路3:二進(jìn)制拆分優(yōu)化
拆分要點(diǎn)
多重背包解題思路4:單調(diào)隊(duì)列
模板題
【代碼】
0、背包問題分類
背包問題可分為0/1背包簡化版，背包方案數(shù)，完全背包，分組背包，多重背包等
1、?0/1背包簡化版
0/1背包的簡化版：不管物品的價(jià)值。把體積看成最優(yōu)化目標(biāo)：最大化體積。?
裝箱問題????????lanqi ao0J題號(hào)763
題目描述
有一個(gè)箱子容量為?V（正整數(shù)，0≤V≤20000），同時(shí)有?n?個(gè)物品（0≤n≤30），每個(gè)物品有一個(gè)體積（正整數(shù)）。
要求?n?個(gè)物品中，任取若干個(gè)裝入箱內(nèi)，使箱子的剩余空間為最小。
輸入描述
輸入第一行，一個(gè)整數(shù)，表示箱子容量。
第二行，一個(gè)整數(shù)?n，表示有?n?個(gè)物品。
接下來?n?行，分別表示這?n?個(gè)物品的各自體積。
輸出描述
輸出一行，表示箱子剩余空間。
輸入輸出樣例
輸入
24 6 8 3 12 7 9 7輸出
0
0/1背包的簡化版，不管物品的價(jià)格。把體積（不是價(jià)格）看成最優(yōu)化目標(biāo):最大化體積。
【代碼】
dp = [0]*20010
V = int(input())# 容量
n = int(input())# 物品數(shù)
c = [0]*40 # 存每個(gè)物品體積
# 讀入每個(gè)物體的體積
for i in range(1, n+1): c[i]=int(input ())
# 自我滾動(dòng)
for i in range (1, n+1) :for j in range (V, c[i]-1,-1):dp[j] = max(dp[j],dp[j-c[i]]+c[i])
print(V-dp[V]) # 剩余最小容量 = 容量 - 物品最大體積2、0/ 1背包的方案數(shù)
2022年屆國賽，填空題，langiao0J題號(hào)2186
問題描述
將 2022 拆分成 10 個(gè)互不相同的正整數(shù)之和, 總共有多少種拆分方法?
注意交換順序視為同一種方法, 例如 2022=1000+1022?和?2022=1022+1000?就視為同一種方法。
答案提交
這是一道結(jié)果填空的題, 你只需要算出結(jié)果后提交即可。本題的結(jié)果為一 個(gè)整數(shù), 在提交答案時(shí)只填寫這個(gè)整數(shù), 填寫多余的內(nèi)容將無法得分。
【思路】
- 題目求10個(gè)數(shù)的組合情況，這十個(gè)數(shù)相加等于2022。因?yàn)槭翘羁疹}可以不管運(yùn)行時(shí)間，看起來可以用暴力for循環(huán)10次，加上剪枝。然而暴力的時(shí)間極長，因?yàn)榇鸢甘?379187662194355221。
- 建模：這一題其實(shí)是0/1背包：背包容量為2022，物品體積為1~2022，往背包中裝10個(gè)物品，要求總體積為2022，問一共有多少種方案。
- 與標(biāo)準(zhǔn)背包的區(qū)別:是求方案總數(shù)。
?【做法】
- 定義dp[ ][ ][ ]: dp[i][i][k]表示數(shù)字1~i取j個(gè)，容量為k的方案數(shù)。
- 下面的分析沿用標(biāo)準(zhǔn)0/1背包的分析方法。
- 從i-1擴(kuò)展到i，分兩種情況:
????????(1) k>i：數(shù)i可以要，也可以不要。
? ? ? ? ? ? ?要i：? ?從1~i-1中取j-1個(gè)數(shù)，再取i，等價(jià)于dp[i-1][j-1][k-i]。
? ? ? ? ? ? ?不要i：從1~i-1中取j個(gè)數(shù)，等價(jià)于dp[i-1][i][k]
?????????????合起來（要和不要的總方案數(shù)）: dp[i][i][k] = dp[i-1][i][k] + dp[i-1][j-1][k-i]
????????( 2) k<i：由于數(shù)i比總和k還大，顯然i不能用。有: dp[i][i][k]= dp[i-1][ji][k]
【代碼】
空間優(yōu)化1：交替滾動(dòng)
dp = [[[0]*2222 for i in range(11)] for j in range(2222)] # 比題目要求的數(shù)據(jù)范圍大一點(diǎn)
for i in range(0,2023): dp[i][0][0]=1 # 初始化：遞推條件的初始值，不選也是一種方案
for i in range(1,2023):for j in range(1,11):for k in range(1,2023):if k<i: dp[i][j][k] = dp[i-1][j][k]else:dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-1][k-i]
print(dp[2022][10][2022])空間優(yōu)化2：自我滾動(dòng)
dp = [[0]*2222 for i in range(11)]
dp[0][0] = 1 #特別注意這個(gè)初始化
for i in range(1,2023):for j in range (10,0,-1): # 10個(gè)數(shù)for k in range(i,2023): # k>=idp[j][k] += dp[j-1][k-i]
print(dp[10][2022])?3、完全背包
- 特點(diǎn)：每種物品有無窮多個(gè)?
小明的背包2lanqiao0J題號(hào)1175
題目描述
小明有一個(gè)容量為?V?的背包。
這天他去商場(chǎng)購物，商場(chǎng)一共有?N?種物品，第?i?種物品的體積為 wi?，價(jià)值為?vi?，每種物品都有無限多個(gè)。
小明想知道在購買的物品總體積不超過?V?的情況下所能獲得的最大價(jià)值為多少，請(qǐng)你幫他算算。
輸入描述
輸入第?1?行包含兩個(gè)正整數(shù) N,V，表示商場(chǎng)物品的數(shù)量和小明的背包容量。
第 2～N+1?行包含?2?個(gè)正整數(shù) w,v，表示物品的體積和價(jià)值。
1≤N≤10^3，1≤V≤10^3，1≤wi?,vi?≤10^3。
輸出描述
輸出一行整數(shù)表示小明所能獲得的最大價(jià)值。
輸入輸出樣例
輸入
5 20 1 6 2 5 3 8 5 15 3 3輸出
120
【思路】
和0/1背包類似。0/1背包的每種物品只有1件，完全背包的每種物品有無窮多件，第i種可以裝0件、1件、2件、.....、件。
做法：定義dp[i][j]：把前i種物品（從第1種到第i種）裝入容量為j的背包中獲得的最大價(jià)值。把每個(gè)dp[i][j]都看成一個(gè)背包：背包容量為j，裝1~i這些物品。最后得到的dp[N][C]就是問題的答案:把N種物品裝進(jìn)容量C的背包的最大價(jià)值。
區(qū)別：在0/1背包問題中，每個(gè)物品只有拿與不拿兩種;而完全背包問題，需要考慮拿幾個(gè)
【代碼】
完全背包的代碼和0/1背包的代碼相似，只多了一個(gè)k循環(huán)，用來遍歷每種物品拿幾個(gè)。
def solve(n,C) :for i in range (1, n+1):for j in range (0,C+1):dp[i][j] = dp[i - 1][j] # 初始化為都不裝的情況for k in range(1,j//c[i]+1): # 可以拿1~j//c[i]個(gè)該物品 k*c[i]<=j #在容量為j的背包中放k個(gè)dp[i][j] = max(dp[i][j],dp[i - 1][j - k * c[i]] +k * w[i])return dp[n][C]N = 3011
dp = [[0]*N for j in range(N)]
w =[0]*N; c = [0]*N
n,C = map(int,input().split())
for i in range(1, n+1):c[i], w[i] = map(int,input ().split()) # 每個(gè)物品的體積和價(jià)值
print(solve(n,C))也可以不需要初始化條件，但下面要從0個(gè)該物品開始遍歷，這樣寫代碼更加簡潔，但時(shí)間復(fù)雜度高了一點(diǎn)，代碼如下：
def solve(n,C) :for i in range (1, n+1):for j in range (0,C+1):dp[i][j] = dp[i - 1][j] # 初始化為都不裝的情況for k in range(1,j//c[i]+1): # 可以拿1~j//c[i]個(gè)該物品 k*c[i]<=j #在容量為j的背包中放k個(gè)dp[i][j] = max(dp[i][j],dp[i - 1][j - k * c[i]] +k * w[i])return dp[n][C]N = 3011
dp = [[0]*N for j in range(N)]
w =[0]*N; c = [0]*N
n,C = map(int,input().split())
for i in range(1, n+1):c[i], w[i] = map(int,input ().split()) # 每個(gè)物品的體積和價(jià)值
print(solve(n,C))4、分組背包?
?分組背包問題:
- 有一些物品，把物品分為n組，其中第i組第k個(gè)物品體積是c[i][k]，價(jià)值是w[i][k];
- 每組內(nèi)的物品沖突，每組內(nèi)最多只能選出一個(gè)物品;
- 給定一個(gè)容量為C的背包，問如何選物品，使得裝進(jìn)背包的物品的總價(jià)值最大。
解題思路與0/1背包相似。
- 0/1背包dp[i][j]：把前i個(gè)物品（從第1個(gè)到第i個(gè)）裝入容量為j的背包中獲得的最大價(jià)值。
- 分組背包dp[i][j]：把前i組物品裝進(jìn)容量j的背包（每組最多選一個(gè)物品)，可獲得的最大價(jià)值。
- 狀態(tài)轉(zhuǎn)移方程：
? ? ? ? ? ? ? ? ? ? ? ? ?dp[i][j] = max {dp[i-1][j]，dp[i-1][j-c[i][k]] + w[i][k]}? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? dp[i-1][j]表示第i組不選物品，dp[i-1][j-c[i][k]]表示第i組選第k個(gè)物品。 - 求解方程需要做i、j、k的三重循環(huán)。
核心代碼：
狀態(tài)轉(zhuǎn)移方程:dp[i][j] = max {dp[i-1][j], dp[i-1][j-c[i][k]] + w[i][k]}，用滾動(dòng)數(shù)組，變?yōu)?dp[j] = max {dp[j]，dp[j-c[i][k]]+ w[i][k]}
dp = [0] * N
for i in range(1, n + 1): # 遍歷每個(gè)組for j in range(C, -1, -1): # 枚舉容量for k in range(1, C + 1): # 用k枚舉第i組的所有物品if j >= c[i][k]: # 第k個(gè)物品能裝進(jìn)容量j的背包dp[j] = max(dp[j], dp[j - c[i][k]] + w[i][k]) # 第i組第k個(gè)
print(dp[C])5、多重背包
多重背包問題:
- 給定n種物品和一個(gè)背包，第i種物品的體積是ci，價(jià)值為wi，并且有mi個(gè)，背包的總?cè)萘繛镃。
- 如何選擇裝入背包的物品，使得裝入背包中的物品的總價(jià)值最大?
- 與完全背包的區(qū)別：完全背包是每種物品都有無限多個(gè)，而多重背包是有限個(gè)
多重背包解題思路1:轉(zhuǎn)化為0/1背包
- 轉(zhuǎn)換為0/1背包問題。
- 把相同的
個(gè)第i種物品看成獨(dú)立的
個(gè)物品，。
- 然后按0/1背包求解，復(fù)雜度
。
多重背包解題思路2:直接DP
- 定義狀態(tài)dpli][j]:表示把前i個(gè)物品裝進(jìn)容量j的背包，能裝進(jìn)背包的最大價(jià)值。
- 第i個(gè)物品分為裝或不裝兩種情況，狀態(tài)轉(zhuǎn)移方程:
????????????????????????????????dp[i][j] = max {dp[i-1][j]，dp[i-1][j-k*c[i]] ＋k*w[i]}
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1 ≤k ≤min{m[i], j/c[i]}? ? ? ? ? ? ?# k不能超過?個(gè)和最大容量個(gè)數(shù)的最小值
- 直接寫i、j、k三重循環(huán)，復(fù)雜度和第一種思路的復(fù)雜度一樣。
- 對(duì)比完全背包:1≤k ≤ j/c[i]
核心代碼：?
????????狀態(tài)轉(zhuǎn)移方程:dp[i][j] = max {dp[i-1][j], dp[i-1][j-k*c[i]]+ k*w[i]}，用滾動(dòng)數(shù)組，變?yōu)?dp[j] = max{dp[j]，dp[j-k*c[i]]＋ k*w[i]}。
dp = [0]*N
for i in range(1, n+1): #枚舉物品for j in range (C,c[i]-1,-1): #枚舉背包容量for k in range(1,m[i]+1): #用k遍歷第i組的所有物品if(j >= k*c[i]): #第k個(gè)物品能裝進(jìn)容量j的背包dp[j] = max(dp[j], dp[j-k*c[i]]+k*w[i])
print(dp[C])?多重背包解題思路3:二進(jìn)制拆分優(yōu)化
- 一種簡單而有效的技巧。
- 例如第i種物品有
- 不過要組合成26種情況，其實(shí)并不需要25個(gè)物品。
- 根據(jù)二進(jìn)制的計(jì)算原理，一個(gè)十進(jìn)制整數(shù)X，可以用1、2、4、8、...這些2的倍數(shù)相加得到，例如25=16+8+1，這些2的倍數(shù)只有logX個(gè)。
- 題目中第i種物品有
優(yōu)化到
。
拆分要點(diǎn)：
- 注意拆分的具體實(shí)現(xiàn)，不能全部拆成2的倍數(shù)，而是先按2的倍數(shù)從小到大拆，最后是一個(gè)小于等于最大倍數(shù)的余數(shù)。
- 保證拆出的數(shù)相加在[1, mi]范圍內(nèi)，不會(huì)大于mi。
- 例如mi= 25，把它拆成1、2、4、8、10，最后是余數(shù)10，10<16，這5個(gè)數(shù)能組合成1~25內(nèi)的所有數(shù)字，不會(huì)超過25。
- 錯(cuò)誤示例：如果把25拆成1、2、4、8、16，相加的范圍就是[1,31]了。
多重背包解題思路4:單調(diào)隊(duì)列
因?yàn)檫@一講主要是講dp算法，所以就不在直接過多介紹其他算法，但這個(gè)方法優(yōu)化程度更高，有興趣的朋友可以看看這篇文章：單調(diào)隊(duì)列優(yōu)化多重背包（全網(wǎng)最詳細(xì)解析）?
模板題
【輸入描述】第一行是整數(shù)n和C，分別表示物品種數(shù)和背包的最大容量。接下來 n行，每行三個(gè)整數(shù) wi、ci、mi，分別表示第i個(gè)物品的價(jià)值、體積、數(shù)量。
【輸出描述】輸出一個(gè)整數(shù)，表示背包不超載的情況下裝入物品的最大價(jià)值。
【輸入樣例】
4 20
3 9 3
5 9 1
9 4 2
8 1 3
【輸出樣例】
47
【代碼】
?代碼用二進(jìn)制拆分優(yōu)化來解答。
N = 100010
w = [0] * N;c = [0] * N;m = [0] * N
xw = [0] * N;xc = [0] * N # 經(jīng)過二進(jìn)制拆分后的新體積和新價(jià)值，轉(zhuǎn)換后每個(gè)物體只有一個(gè)，所以沒有新的數(shù)量n, C = map(int, input().split())
for i in range(1, n + 1):w[i], c[i], m[i] = map(int, input().split())# 以下是二進(jìn)制拆分
xn = 0 # 二進(jìn)制拆分后的新物品總數(shù)量
for i in range(1, n + 1):j = 1while j <= m[i]: # 例:直到最后一個(gè)數(shù)m[i]（余數(shù)）出現(xiàn)m[i] -= j # 減去已拆分的xn += 1xc[xn] = j * c[i] # 新物品的體積xw[xn] = j * w[i]j <<= 1 # 二進(jìn)制枚舉:1,2,4...if m[i] > 0: # 最后一個(gè)是余數(shù)xn += 1xc[xn] = m[i] * c[i]xw[xn] = m[i] * w[i]
# 以下是滾動(dòng)數(shù)組版本的0/1背包
dp = [0] * N
for i in range(1, xn + 1): # 枚舉物品for j in range(C, xc[i] - 1, -1): # 枚舉背包容量 xc[i] - 1這里的-1是因?yàn)閞ange函數(shù)是左閉右開區(qū)間，-1才能取到xc[i]dp[j] = max(dp[j], dp[j - xc[i]] + xw[i])
print(dp[C])