文章目錄

• 動态規劃——背包問題(3)
• • 求解最佳方案數
  • • 例題
    • • 思路
      • 代碼
  • 混合背包問題
  • • 例題
    • • 思路
      • 代碼
  • 有依賴的背包問題
  • • 例題
    • 思路
    • 代碼
  • 考察思維的一些背包題目
  • • 機器配置設定
    • 金明的預算方案
    • 貨币系統
    • 能量石
  • 總結

動态規劃——背包問題(3)

求解最佳方案數

例題

有 N 件物品和一個容量是 V 的背包。每件物品隻能使用一次。

第 i 件物品的體積是 vi，價值是 wi。

求解将哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。

輸出 最優選法的方案數。注意答案可能很大，請輸出答案模 109+7 的結果。

輸入格式

第一行兩個整數，N，V，用空格隔開，分别表示物品數量和背包容積。

接下來有 N 行，每行兩個整數 vi,wi，用空格隔開，分别表示第 i 件物品的體積和價值。

輸出格式

輸出一個整數，表示 方案數 模 109+7 的結果。

資料範圍

0<N,V≤1000

0<vi,wi≤1000

輸入樣例

4 5

1 2

2 4

3 4

4 6

輸出樣例：

2

思路

代碼

N = 1010
MOD = int(1e9) + 7
f, g = [0] * N, [1] * N

for i in range(n) :
	v, w = map(int, input().split())
	for j in range(m, v - 1, -1) :
		maxv = max(f[j], f[j - v] + w)
		s = 0
		if maxv == f[j] : s = g[j]
		if maxv == f[j - v] + w : s = (s + g[j - v]) % MOD
		g[j] = s
		f[j] = maxv
print(g[m])
           

混合背包問題

例題

有 N 種物品和一個容量是 V 的背包。

物品一共有三類：

第一類物品隻能用1次（01背包）；

第二類物品可以用無限次（完全背包）；

第三類物品最多隻能用 si 次（多重背包）；

每種體積是 vi，價值是 wi。

求解将哪些物品裝入背包，可使物品體積總和不超過背包容量，且價值總和最大。

輸出最大價值。

輸入格式

第一行兩個整數，N，V，用空格隔開，分别表示物品種數和背包容積。

接下來有 N 行，每行三個整數 vi,wi,si，用空格隔開，分别表示第 i 種物品的體積、價值和數量。

si=−1 表示第 i 種物品隻能用1次；

si=0 表示第 i 種物品可以用無限次；

si>0 表示第 i 種物品可以使用 si 次；

輸出格式

輸出一個整數，表示最大價值。

資料範圍

0<N,V≤1000

0<vi,wi≤1000

−1≤si≤1000

輸入樣例

4 5

1 2 -1

2 4 1

3 4 0

4 5 2

輸出樣例：

8

思路

代碼

N = 1010
f = [0] * N

n, m = map(int, input().split())

for i in range(n) :
	v, w, s = map(int, input().split())
	if s == 0 :
		for j in range(v, m + 1) :
			f[j] = max(f[j], f[j - v] + w)
	else :
		if s == -1 :
			s = 1
		k = 1
		while k <= s :
			for j in range(m, k * v - 1, -1) :
				f[j] = max(f[j], f[j - k * v] + k * w)
			s -= k
			k *= 2
		if s :
			for j in range(m, s * v - 1, -1) :
				f[j] = max(f[j], f[j - s * v] + s * w)
print(f[m])
           

有依賴的背包問題

例題

有 N 個物品和一個容量是 V 的背包。

物品之間具有依賴關系，且依賴關系組成一棵樹的形狀。如果選擇一個物品，則必須選擇它的父節點。

如下圖所示：

如果選擇物品5，則必須選擇物品1和2。這是因為2是5的父節點，1是2的父節點。

每件物品的編号是 i，體積是 vi，價值是 wi，依賴的父節點編号是 pi。物品的下标範圍是 1…N。

求解将哪些物品裝入背包，可使物品總體積不超過背包容量，且總價值最大。

輸出最大價值。

輸入格式

第一行有兩個整數 N，V，用空格隔開，分别表示物品個數和背包容量。

接下來有 N 行資料，每行資料表示一個物品。

第 i 行有三個整數 vi,wi,pi，用空格隔開，分别表示物品的體積、價值和依賴的物品編号。

如果 pi=−1，表示根節點。 資料保證所有物品構成一棵樹。

輸出格式

輸出一個整數，表示最大價值。

資料範圍

1≤N,V≤100

1≤vi,wi≤100

父節點編号範圍：

内部結點：1≤pi≤N;

根節點 pi=−1;

輸入樣例

5 7

2 3 -1

2 2 1

3 5 1

4 7 2

3 6 2

輸出樣例：

11

思路

代碼

N = 110
f = [[0] * N for _ in range(N)]
h = [-1] * N
e = [0] * N
ne = [-1] * N
v, w = [0] * N, [0] * N
idx = 0

def add(a, b) :
	global idx
	e[idx] = b
	ne[idx] = h[a]
	h[a] = idx
	idx += 1
	
def dfs(u) :
	for i in range(v[u], m + 1) : f[u][i] = w[u] # 目前節點必選
	i = h[u]
	while i != -1 : #枚舉u的子樹i組
		son = e[i]
		dfs(son)
		for j in range(m, v[u] - 1, -1) : #由于第i組不能重複選擇，是以要倒序
			for k in range(j - v[u] + 1) : #枚舉除去目前節點的體積，子節點還能配置設定的體積
				f[u][j] = max(f[u][j], f[u][j - k] + f[son][k])
		i = ne[i]
	
n, m = map(int, input().split())

root = 0
for i in range(1, n + 1) :
	v[i], w[i], p = map(int, input().split())
	if p == -1 :
		root = i
	else :
		add(p, i)
dfs(root)
print(f[root][m])
           

考察思維的一些背包題目

機器配置設定

總公司擁有 M 台 相同 的高效裝置，準備分給下屬的 N 個分公司。

各分公司若獲得這些裝置，可以為國家提供一定的盈利。盈利與配置設定的裝置數量有關。

問：如何配置設定這M台裝置才能使國家得到的盈利最大？

求出最大盈利值。

配置設定原則：每個公司有權獲得任意數目的裝置，但總台數不超過裝置數 M。

輸入格式

第一行有兩個數，第一個數是分公司數 N，第二個數是裝置台數 M；

接下來是一個 N×M 的矩陣，矩陣中的第 i 行第 j 列的整數表示第 i 個公司配置設定 j 台機器時的盈利。

輸出格式

第一行輸出最大盈利值；

接下 N 行，每行有 2 個數，即分公司編号和該分公司獲得裝置台數。

答案不唯一，輸出任意合法方案即可。

資料範圍

1≤N≤10,

1≤M≤15

輸入樣例：

3 3

30 40 50

20 30 50

20 25 30

輸出樣例：

70

1 1

2 1

3 1

1. 思路

   

2. 代碼

N = 10

f = [[0] * N for _ in range(N)]
a = [[0] * N for _ in range(N)]
ways = [0] * N

n, m = map(int, input().split())

for i in range(1, n + 1) :
	a[i][1 : m + 1] = list(map(int, input().split()))

for i in range(1, n + 1) :
	for j in range(m + 1) :
		for k in range(j + 1) :
			f[i][j] = (f[i][j], f[i - 1][j - k] + a[i][k])

print(f[n][m])

j = m
for i in range(n, 0, -1) :
	for k in range(j + 1) :
		if f[i][j] == f[i - 1][j - k] + a[i][k] :
			ways[i] = k
			j -= k
			break
for i in range(1, n + 1) :
	print(i, ways[i])
           

金明的預算方案

金明今天很開心，家裡購置的新房就要領鑰匙了，新房裡有一間金明自己專用的很寬敞的房間。

更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎麼布置，你說了算，隻要不超過N元錢就行”。

今天一早，金明就開始做預算了，他把想買的物品分為兩類：主件與附件，附件是從屬于某個主件的，下表就是一些主件與附件的例子：

如果要買歸類為附件的物品，必須先買該附件所屬的主件。

每個主件可以有0個、1個或2個附件。

附件不再有從屬于自己的附件。

金明想買的東西很多，肯定會超過媽媽限定的N元。

于是，他把每件物品規定了一個重要度，分為5等：用整數1~5表示，第5等最重要。

他還從網際網路上查到了每件物品的價格（都是10元的整數倍）。

他希望在不超過N元（可以等于N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。

設第j件物品的價格為v[j]，重要度為w[j]，共選中了k件物品，編号依次為j1，j2，…，jk，則所求的總和為：

v[j1]∗w[j1]+v[j2]∗w[j2]+…+v[jk]∗w[jk]（其中*為乘号）

請你幫助金明設計一個滿足要求的購物單。

輸入格式

輸入檔案的第1行，為兩個正整數，用一個空格隔開：N m，其中N表示總錢數，m為希望購買物品的個數。

從第2行到第m+1行，第j行給出了編号為j-1的物品的基本資料，每行有3個非負整數v p q，其中v表示該物品的價格，p表示該物品的重要度（1~5），q表示該物品是主件還是附件。

如果q=0，表示該物品為主件，如果q>0，表示該物品為附件，q是所屬主件的編号。

輸出格式

輸出檔案隻有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的最大值（<200000）。

資料範圍

N<32000,m<60,v<10000

輸入樣例：

1000 5

800 2 0

400 5 1

300 5 1

400 3 0

500 2 0

輸出樣例：

2200

1. 思路

   

2. 代碼

N = 32010
M = 70
f = [0] * N
master = [[0, 0] for _ in range(M)]
serven = [[] for _ in range(M)]

m, n = map(int, input().split())

for i in range(1, n + 1) :
	v, p, q = map(int, input().split())
	if not q :
		master[i] = [v, v * p]
	else :
		serven[q].append([v, v * p])

for i in range(1, n + 1) :
	if master[i][0] :
		for j in range(m, -1, -1) :
			for k in range(1 << len(serven[i])) :
				v, w = master[i][0], master[i][1]
				for u in range(len(serven[i])) :
					if k >> u :
						v += serven[i][u][0]
						w += serven[i][u][1]
				if j >= v :
					f[j] = max(f[j], f[j - v] + w)
print(f[m])
           

貨币系統

在網友的國度中共有 n 種不同面額的貨币，第 i 種貨币的面額為 a[i]，你可以假設每一種貨币都有無窮多張。

為了友善，我們把貨币種數為 n、面額數組為 a[1…n] 的貨币系統記作 (n,a)。

在一個完善的貨币系統中，每一個非負整數的金額 x 都應該可以被表示出，即對每一個非負整數 x，都存在 n 個非負整數 t[i] 滿足 a[i]×t[i] 的和為 x。

然而，在網友的國度中，貨币系統可能是不完善的，即可能存在金額 x 不能被該貨币系統表示出。

例如在貨币系統 n=3, a=[2,5,9] 中，金額 1,3 就無法被表示出來。

兩個貨币系統 (n,a) 和 (m,b) 是等價的，當且僅當對于任意非負整數 x，它要麼均可以被兩個貨币系統表出，要麼不能被其中任何一個表出。

現在網友們打算簡化一下貨币系統。

他們希望找到一個貨币系統 (m,b)，滿足 (m,b) 與原來的貨币系統 (n,a) 等價，且 m 盡可能的小。

他們希望你來協助完成這個艱巨的任務：找到最小的 m。

輸入格式

輸入檔案的第一行包含一個整數 T，表示資料的組數。

接下來按照如下格式分别給出 T 組資料。

每組資料的第一行包含一個正整數 n。

接下來一行包含 n 個由空格隔開的正整數 a[i]。

輸出格式

輸出檔案共有 T 行，對于每組資料，輸出一行一個正整數，表示所有與 (n,a) 等價的貨币系統 (m,b) 中，最小的 m。

資料範圍

1≤n≤100,

1≤a[i]≤25000,

1≤T≤20

輸入樣例：

2

4

3 19 10 6

5

11 29 13 19 17

輸出樣例：

2

5

1. 思路

   一些性質：

   • a1, a2,…,an一定都可以被表示出來
   • 在最優解中，b1,b2,…, bn一定是從a1,a2, …,an中選擇
   • b1，b2，…,bn一定不能被其他bi表示
2. 代碼

N = 25010

T = int(input())

for t in range(T) :
	f = [0] * N
	n = int(input())
	nums = list(map(int, input().split()))
	nums.sort()
	m = nums[n - 1]
	res = 0
	f[0] = 1
	for i in range(1, n + 1) :
		if not f[nums[i - 1]] : res += 1
		for j in range(nums[i - 1] -1, m + 1) :
			f[j] += f[j - nums[i - 1]]
			
	print(res)
           

能量石

岩石怪物杜達生活在魔法森林中，他在午餐時收集了 N 塊能量石準備開吃。

由于他的嘴很小，是以一次隻能吃一塊能量石。

能量石很硬，吃完需要花不少時間。

吃完第 i 塊能量石需要花費的時間為 Si 秒。

杜達靠吃能量石來擷取能量。

不同的能量石包含的能量可能不同。

此外，能量石會随着時間流逝逐漸失去能量。

第 i 塊能量石最初包含 Ei 機關的能量，并且每秒将失去 Li 機關的能量。

當杜達開始吃一塊能量石時，他就會立即獲得該能量石所含的全部能量（無論實際吃完該石頭需要多少時間）。

能量石中包含的能量最多降低至 0。

請問杜達通過吃能量石可以獲得的最大能量是多少？

輸入格式

第一行包含整數 T，表示共有 T 組測試資料。

每組資料第一行包含整數 N，表示能量石的數量。

接下來 N 行，每行包含三個整數 Si,Ei,Li。

輸出格式

每組資料輸出一個結果，每個結果占一行。

結果表示為 Case #x: y，其中 x 是組别編号（從 1 開始），y 是可以獲得的最大能量值。

資料範圍

1≤T≤10,

1≤N≤100,

1≤Si≤100,

1≤Ei≤105,

0≤Li≤105

輸入樣例：

3

4

20 10 1

5 30 5

100 30 1

5 80 60

3

10 4 1000

10 3 1000

10 8 1000

2

12 300 50

5 200 0

輸出樣例：

Case #1: 105

Case #2: 8

Case #3: 500

樣例解釋

在樣例＃1中，有 N=4 個寶石。杜達可以選擇的一個吃石頭順序是：

吃第四塊石頭。這需要 5 秒，并給他 80 機關的能量。

吃第二塊石頭。這需要 5 秒，并給他 5 機關的能量（第二塊石頭開始時具有 30 機關能量，5 秒後失去了 25 機關的能量）。

吃第三塊石頭。這需要 100 秒，并給他 20 機關的能量（第三塊石頭開始時具有 30 機關能量，10 秒後失去了 10 機關的能量）。

吃第一塊石頭。這需要 20 秒，并給他 0 機關的能量（第一塊石頭以 10 機關能量開始，110 秒後已經失去了所有的能量）。

他一共獲得了 105 機關的能量，這是能獲得的最大值，是以答案是 105。

在樣本案例＃2中，有 N=3 個寶石。

無論杜達選擇吃哪塊石頭，剩下的兩個石頭的能量都會耗光。

是以他應該吃第三塊石頭，給他提供 8 機關的能量。

在樣本案例＃3中，有 N=2 個寶石。杜達可以：

吃第一塊石頭。這需要 12 秒，并給他 300 機關的能量。

吃第二塊石頭。這需要 5 秒，并給他 200 機關的能量（第二塊石頭随着時間的推移不會失去任何能量！）。

是以答案是 500。

1. 思路

   最優解一定是按照一定順序來吃：假定為a1, a2,…an的順序。

   a i 和 a i + 1 是其中相鄰的兩個能量石 a_i和a_{i+1}是其中相鄰的兩個能量石 ai​和ai+1​是其中相鄰的兩個能量石，按照這個順序吃，假設開始吃的時間為t，則獲得的能量為 S 1 = e i − t ∗ l i + e i + 1 − ( t + s i ) ∗ l i + 1 S_1 = e_i-t*l_i + e_{i + 1} - (t + s_i) * l_{i + 1} S1​=ei​−t∗li​+ei+1​−(t+si​)∗li+1​，如果交換順序則 S 2 = e i + 1 − t ∗ l i + 1 + e i − ( t + s i + 1 ) ∗ l i S_2 = e_{i + 1}-t*l_{i+1} + e_{i} - (t + s_{i+ 1}) * l_{i} S2​=ei+1​−t∗li+1​+ei​−(t+si+1​)∗li​。如果按規定順序，那麼 S 1 > = S 2 S_1 >= S_2 S1​>=S2​,化簡即 s i / l i < = s i + 1 / l i + 1 s_i / l_i <= s_{i + 1} / l_{i + 1} si​/li​<=si+1​/li+1​。則每個物品按照這樣的順序選取才能得到最大，下面就是0-1背包的闆子。

   本題值得注意的是，本題狀态表示是恰好時間j時能量最大值，因為能量會因為時間損耗。

2. 代碼

T = int(input())

for t in range(T) :
	n = int(input())
	stone = []
	m = 0
	for i in range(n) :
		s, e, l = map(int, input().split())
		stone.append([s, e, l])
		m += s
	f = [-100010] * (m + 1)
	f[0] = 0
	stone.sort(key = lambda x : x[0] / max(x[2], 1e-8))
	for i in range(n) :
		s, e, l = stone[i]
		for j in range(m, s - 1, -1) :
			f[j] = max(f[j], f[j - s] + e - (j - s) * l)
	res = 0
	for i in range(m + 1) :
		res = max(res, f[i])
	print(f'Case #{t + 1}: {res}')
           

1. 總結

求最優解，與推進順序相關，既有增量又有損耗的題目，可以假定一個順序，然後假設順序對調比較大小，得到一定單調性。友善後序加以選擇

總結

背包問題就此告一段落，三篇部落格已經涵蓋了背包的大部分題型，奧力給！！！