動态規劃基礎(一)之01背包與完全背包問題

目錄

1. 動态規劃的引入(01背包問題)
2. 01背包問題的空間優化
3. 完全背包問題
4. 相關練習題

以下是正文:

1.動态規劃的引入(01背包問題)

先來這一題：洛谷P1049

題目描述

有一個箱子容量為VV（正整數，0 ≤ \le ≤ V ≤ \le ≤ 200000≤V≤20000），同時有nn個物品（0<n ≤ \le ≤ 300<n≤30，每個物品有一個體積（正整數）。

要求nn個物品中，任取若幹個裝入箱内，使箱子的剩餘空間為最小。

輸入格式

11個整數，表示箱子容量

11個整數，表示有n個物品

接下來n行，分别表示這n個物品的各自體積

輸出格式

11個整數，表示箱子剩餘空間。

輸入輸出樣例

輸入 #1複制

24
6
8
3
12
7
9
7
           

輸出 #1複制

在沒了解動态規劃前, 我們應該會想到用dfs或者dfs來解決這類題目.

但是我們既然要講動态規劃(Dynamic programming), 那就隻能用動态規劃來寫.

我們用 f i , j f_i,_j fi​,j​來表示前i個物品中選擇若幹個, 使得總空間占用為j所産生的價值, V是箱子總容積.

然後就可以對于每個 a i ( 1 ≤ i ≤ V ) a_i(1\le i\le V) ai​(1≤i≤V)進行決策 f i , j f_i,_j fi​,j​選或不選, 找到目前情況下 f i , j f_i,_j fi​,j​的最優解.

時空複雜度應該都是: O ( V N ) O(VN) O(VN).

code:

#include <bits/stdc++.h>
using namespace std;
const int M = 40;
const int T = 200005;
int f[T];
int w[M];
int main()
{
	memset(w, 0, sizeof w);
	memset(f, 0, sizeof f);
	int v, n;
	scanf("%d%d", &v, &n);
	for(int i = 0; i < n; i++) scanf("%d", &w[i]);
	for(int i = 0; i < n; i++)
		for(int j = v; j >= w[i]; j--)
			f[i][j] = max(f[i-1][j], f[i-1][j - w[i]] + w[i]);
	printf("%d", v - f[n-1][v]);
	return 0;
}
           

2. 01背包問題的空間優化

我們發現, 更新每次的 f i , j f_{i,j} fi,j​隻會用到 f i − 1 , j − k ( k > = 0 ) f_{i-1,j-k}(k>=0) fi−1,j−k​(k>=0), 是以對于 f i , j f_i,_j fi​,j​, 若j從V開始每次減一, f i , j − k = f i − 1 , j − k f_{i, j-k} = f_{i-1,j-k} fi,j−k​=fi−1,j−k​.

是以我們可以将 f i , j f_{i,j} fi,j​化簡為 f j f_j fj​.

此時, 空間複雜度便優化至: O ( V ) O(V) O(V).

code:

#include <bits/stdc++.h>
using namespace std;
const int M = 40;
const int T = 200005;
int f[T];
int w[M];
int main()
{
	memset(w, 0, sizeof w);
	memset(f, 0, sizeof f);
	int v, n;
	scanf("%d%d", &v, &n);
	for(int i = 0; i < n; i++) scanf("%d", &w[i]);
	for(int i = 0; i < n; i++)
		for(int j = v; j >= w[i]; j--)
			f[j] = max(f[j], f[j - w[i]] + w[i]);
	printf("%d", v - f[v]);
	return 0;
}
           

3.完全背包問題

再看一題:洛谷P1616.

題目背景

此題為紀念 LiYuxiang 而生。

題目描述

LiYuxiang 是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫師。為此，他想拜附近最有威望的醫師為師。醫師為了判斷他的資質，給他出了一個難題。醫師把他帶到一個到處都是草藥的山洞裡對他說：“孩子，這個山洞裡有一些不同種類的草藥，采每一種都需要一些時間，每一種也有它自身的價值。我會給你一段時間，在這段時間裡，你可以采到一些草藥。如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大。”

如果你是 LiYuxiang，你能完成這個任務嗎？

此題和原題的不同點：

\11. 每種草藥可以無限制地瘋狂采摘。

\22. 藥的種類眼花缭亂，采藥時間好長好長啊！師傅等得菊花都謝了！

輸入格式

輸入第一行有兩個整數，分别代表總共能夠用來采藥的時間 tt 和代表山洞裡的草藥的數目 mm。

第 22 到第 (m + 1)(m+1) 行，每行兩個整數，第 (i + 1)(i+1) 行的整數 a_i, b_ia**i,b**i 分别表示采摘第 ii 種草藥的時間和該草藥的價值。

輸出格式

輸出一行，這一行隻包含一個整數，表示在規定的時間内，可以采到的草藥的最大總價值。

輸入輸出樣例

輸入 #1複制

70 3
71 100
69 1
1 2
           

輸出 #1複制

140
           

說明/提示

資料規模與約定

• 對于 30%30% 的資料，保證 m \le 10^3m≤103 。
• 對于 100%100% 的資料，保證 1 \leq m \le 10^41≤m≤104，1 \leq t \leq 10^71≤t≤107，且 m \times t < 10^7m×t<107，1 \leq a_i, b_i \leq 10^41≤a**i,b**i≤104。

這題很明顯于上一題不同，這一題對于物品選擇次數沒有限制，是以一個物品有多種狀态；而上一題一個物品之允許選或不選，隻有兩種狀态.

其實，我們将01背包空間優化版的代碼稍微修改，就得到了本題的代碼.

我們發現，将:

替換為:

不難發現, 此時一個物品可以被選擇多次.

時空複雜度不變, 見下:

時間複雜度: O ( V N ) O(VN) O(VN), 空間複雜度: O ( V ) O(V) O(V).

code:

#include <bits/stdc++.h>
using namespace std;
const int M = 10005;
const int T = 10000005;
int f[T];
int w[M], v[M];
int main()
{
	memset(v, 0, sizeof v);
	memset(w, 0, sizeof w);
	memset(f, 0, sizeof f);
	int V, n;
	scanf("%d%d", &V, &n);
	for(int i = 0; i < n; i++) scanf("%d%d", &w[i], &v[i]);
	for(int i = 0; i < n; i++)
		for(int j = w[i]; j <= V; j++)
			f[j] = max(f[j], f[j - w[i]] + v[i]);
	printf("%d", f[V]);
	return 0;
}
           

4.相關練習題

01背包:

洛谷P1048

洛谷P1049

洛谷P1060

完全背包:

（完全背包的題有點不好找QWQ）

洛谷P1616

NOTE：換了個紅軸鍵盤，打字舒服多了.

JiansYuan

2020.8.15