【資料結構與演算法】-＞演算法-＞動態規劃（上）-＞初識動態規劃-＞怎么精準地幫助女朋友薅羊毛-有解無憂

動態規劃（上）

- Ⅰ 前言
- Ⅱ 0-1 背包問題
- Ⅲ 0-1 背包問題 Plus
- Ⅳ 如何利用動態規劃來湊滿減

Ⅰ 前言

淘寶的雙十一大家相比都經歷過，雙十一里有很多滿級訓動，比如“滿 200 元減 50 元”，假如你的女朋友的購物車中有 n 個（n > 100）想買的商品，她希望能從里面選出來幾個，在湊夠滿減條件的前提下，選出來的商品價格總和最大程度地接近滿減條件（200 元），這樣就可以極大限度地“薅羊毛”，作為程式員的你，能不能換個女朋友？奧不對，能不能寫個代碼幫她搞定這件事呢？

要想高效地解決這個問題，就要用到這篇文章要講的動態規劃（Dynamic Programming），

動態規劃比較適合用來求解最優問題，比如求最大值、最小值等等，它可以非常顯著地降低時間復雜度，提高代碼的執行效率，不過，動態規劃也是出了名的難學，對于新手入門很不容易，但是，只要入了門，就一馬平川了，

這篇文章，我先來帶大家從兩個經典動態規劃的問題模型入手，先理解一下動態規劃的思想，在后面的兩篇文章，我再從理論層面和與其他思想的比較著手，深入了解動態規劃，最后再通過實戰應用，解決三個非常經典的動態規劃的問題，我們就開始吧，

Ⅱ 0-1 背包問題

在前面講貪心演算法和回溯演算法的文章中，我提到了很多次背包問題，我們再從動態規劃來看看這個問題，

對于一組不同重量、不可分割的物品，我們需要選擇一些裝入背包，在滿足背包最大重量限制的前提下，背包中物品總重量的最大值是多少呢？

回溯法處理這類問題就是窮舉所有可能的裝法，然后找出滿足條件的最大值，不過，回溯演算法的時間復雜度比較高，是指數級別的，那有沒有什么規律，是我們可以找到用以降低時間復雜度的呢？

public void findSolve(int index, int currentWeight, int[] items, 
													int num, int weight) {	
		if (currentWeight == weight || index == num) { //已經裝滿 || 考察完所有物品
			if (currentWeight > maxWeight) {
				maxWeight = currentWeight;
				return;
			}
		}
		findSolve(index + 1, currentWeight, items, num, weight); //items[index]的物品不裝進背包
		if (currentWeight + items[index] <= weight) {
			findSolve(index + 1, currentWeight + items[index], items, num, weight);//裝進背包
		}
	}
}

規律是很不好找，我們來畫一張圖，假設背包的最大承載重量是 9，我們有 5 個不同的物品，每個物品的重量分別是 2，2，4，6，3，如果我們把這個例子的回溯求解程序，用遞回樹畫出來，就是下面這個的樣子：

在這里插入圖片描述
遞回樹中的每個節點表示一種狀態，我們用 (i, cw) 來表示，其中 i 表示將要決策第幾個物品是否要放入背包，cw 表示當前背包中物品的總重量，比如，(2， 2) 表示我們將要決策第 2 個物品是否裝入背包，在決策前，背包中物品的總重量是 2，

從遞回樹中，你應該能發現，有些子問題的求解是重復的，比如圖中 f(2, 2) 和 f(3, 4) 都被重復計算了兩次，我們可以用“備忘錄”的方法解決這個問題：記錄已經計算好的 f(i, cw)，當再次計算到重復的 f(i, cw) 的時候，就可以直接從備忘錄中取出來用， 這樣就不用再遞回計算了，可以避免很多冗余計算，

package com.tyz.core;

public class ZeroOneBackpack {
	private int maxWeight = Integer.MIN_VALUE; //結果放在maxWeight中
	private int[] weights = {2, 2, 4, 6, 3}; //物品重量
	private int num = 5; //物品個數
	private int weight = 9; //背包承受的最大重量
	private boolean[][] mem = new boolean[5][10]; //備忘錄，默認值為false

	public ZeroOneBackpack() {}
	
	public void findSolve(int i, int cw) {
		if (cw == weight || i == num) {
			if (cw > maxWeight) {
				maxWeight = cw;
			}
			return;
		}
		if (mem[i][cw]) {
			return; //重復狀態
		}
		mem[i][cw] = true; //記錄(i, cw)這個狀態
		findSolve(i + 1, cw); //選擇不裝第i個物品
		if (cw + weights[i] <= weight) {
			findSolve(i + 1, cw + weights[i]); //選擇裝第i個物品
		}
	}
}

這種解決方法非常好，實際上，它已經和動態規劃的執行效率基本上沒有差別，但是，多一種方法就多一種解決思路，我們現在來看看動態規劃是怎么做的，

我們把整個求解程序分為 n 個階段，每個階段會決策一個物品是否放到背包中，每個物品決策（放入或不放入背包）完之后，背包中的物品的重量會有多種情況，也就是說，會達到多種不同的狀態，對應到遞回樹中，就是有很多不同的節點，

我們把每一次重復的狀態（節點）合并，只記錄不同的狀態，然后基于上一層的狀態集合，來推導下一層的狀態集合，我們可以通過合并每一層重復的狀態，這樣就保證每一層不同狀態的個數都不會超過 w 個（w 表示背包的承載重量），也就是例子中的 9，于是，我們就成功避免了每層狀態個數的指數級增長，

我們用一個二維陣列 states[n][w+1]，來記錄每層可以達到的不同狀態，

第 0 個（下標從 0 開始編號）物品的重量是 2，要么裝入背包，要么不裝入背包，決策完之后，會對應背包的兩種狀態，背包中物品的總重量是 0 或者 2，我們用 states[0][0] = true 和 states[0][2] = true 來表示這兩種狀態，

第 1 個物品的重量也是 2，基于之前的背包狀態，在這個物品決策完之后，不同的狀態有 3 個，背包中物品總重量分別是 0（0 + 0），2（0 + 2 or 2 + 0），4（2 + 2），我們用 states[1][0] = true ，states[1][2] = true，states[1][4] = true 來表示這三種狀態，

以此類推，直到考察完所有的物品后，整個 states 狀態陣列就計算好了，我把整個計算的程序畫了出來，大家可以做個參考，理解這個程序，圖中 0 表示 false，1 表示 true，我們只需要在最后一層，找一個值為 true 的最接近 w（這里是 9）的值，就是背包中物品總重量的最大值，

在這里插入圖片描述

我們直接來看代碼，

package com.tyz.first.core;

/**
 * 動態規劃求0-1背包的裝的物品最大重量
 * @author Tong
 */
public class ZeroOneKnapsack {

	public ZeroOneKnapsack() {
	}
	
	/**
	 * 動態規劃查找0-1背包的解
	 * @param weights 物品的重量
	 * @param num 物品的數量
	 * @param weight 背包承受的最大重量
	 * @return 最大重量
	 */
	public int findSolve(int[] weights, int num, int weight) {
		boolean[][] states = new boolean[num][weight+1];
		states[0][0] = true;
		if (weights[0] <= weight) {
			states[0][weights[0]] = true;
		}
		//動態規劃狀態轉移
		for (int i = 1; i < num; i++) {
			for (int j = 0; j <= weight; j++) { //不把第i個元素裝進背包
				if (states[i-1][j] == true) {
					states[i][j] = states[i-1][j];
				}
			}
			for (int j = 0; j <= weight-weights[i]; j++) { //把第i個元素裝進背包
				if (states[i-1][j] == true) {
					states[i][j+weights[i]] = true;
				}
			}
		}
		for (int i = weight; i >= 0; i--) { //輸出結果
			if (states[num-1][i] == true) {
				return i;
			}
		}
		
		return 0;
	}

}

實際上，這就是一個用動態規劃解決問題的思路，我們把問題分解為多個階段，每個階段對應一個決策，我們記錄每一個階段可達的狀態集合（去掉重復的），然后通過當前階段的狀態集合，來推導下一個階段的狀態集合，動態地往前推進，這也是動態規劃這個名字的由來，

我們可以再和其他幾個演算法做個對比，

貪心演算法： 一條路走到黑，就一次機會，每次選一條最優的路線，
回溯演算法： 一條路走到黑，但是有無數次重來的機會，選錯了就倒回去重新選，
動態規劃： 上帝視角，同時選擇所有的選擇，同時發展出每一個未來

在回溯演算法中，我們解決這個問題的時間復雜度是 O(2ⁿ)，是指數級的，那動態規劃解決方案的時間復雜度是多少呢》我們來分析一下，

這個代碼的時間復雜度非常很好想，耗時最多的部分就是代碼中的兩層 for 回圈，所以時間復雜度是 O(n * w)，n 表示物品個數，w 表示背包可以承載的總重量，

從理論上來講，指數級的時間復雜度肯定要比 O(n*w) 高很多，我們舉個例子來感受一下，

我們假設有 10000 個物品，重量分布在 1 到 15000 之間，背包可以承載的總重量是 30000，如果我們用回溯演算法來解決，用具體的數值表示出時間復雜度，就是 2¹⁰⁰⁰⁰，這是一個相當大的數字了，如果我們用動態規劃解決，用具體的數值表示出時間復雜度，就是 10000 * 30000，雖然看起來也很大，但是 2¹⁰⁰⁰⁰ 比起來，要小太多了，

盡管動態規劃的執行效率比較高，但是就上面的代碼來說，我們需要額外申請一個 n 乘以 w + 1 的二維陣列，對空間的消耗比較多，所以，有時候我們說，動態規劃是一種空間換時間的解決思路，那有沒有什么方法可以降低空間消耗呢？

實際上，我們只需要一個大小為 w+1 的一維陣列就可以解決這個問題，動態規劃狀態轉移的程序，都可以基于這個一維陣列來操作，代碼如下👇

	/**
	 * 一維陣列動態規劃求0-1背包的解
	 * @param items 物品重量
	 * @param num 物品數量
	 * @param weight 背包能承受的最大重量
	 * @return
	 */
	public int findSolve2(int[] items, int num, int weight) {
		boolean[] states = new boolean[weight+1];
		states[0] = true;
		if (items[0] <= weight) {
			states[items[0]] = true;
		}
		//動態規劃
		for (int i = 1; i < num; i++) { //把第i個物品放入背包
			for (int j = weight-items[i]; j >= 0; j--) {
				if (states[j] == true) {
					states[j+items[i]] = true;
				}
			}
		}
		for (int i = weight; i >= 0; i--) { //輸出結果
			if (states[i] == true) {
				return i;
			}
		}
		return 0;
	}

可能這里的代碼還是不太好理解，我再對這個代碼做個解釋，

states 表示的是當前背包總重量所有可能取值的集合，如果將第 i 個物品放入背包，我們需要在當前背包總重量的所有取值中，找到小于等于 j 的，因此 for 回圈中，j = weight-items[i]

還有一個需要特別注意的，for (int j = weight-items[i]; j >= 0; j--)，這里為什么要將 j 遞減的回圈，為什么不還是 j 從 0 開始，用j++回圈？這里其實特別巧妙，

在 for 回圈里有一個 If 的條件陳述句

	if (states[j] == true) {
		states[j+items[i]] = true;	
	}

如果條件成立的話，做的操作是 states[j+items[i]] = true;，大家可以仔細想想，這個操作是不是相當于 states[j + X] = true;，這個+ X，是不是就相當于做了很多次 j++？所以如果 j 從 0 開始遍歷，在前面做了一次這個操作后，后面就會再次遍歷到那個位置，但是由于那個位置對應的 states[j]在前面已經被設定成 true 了，所以再次到這里，就會進行重復運算，影響了真正的結果，

但是如果我們從后向前遍歷，就可以避免這個問題，大家可以再思考一下，

Ⅲ 0-1 背包問題 Plus

基于上面的 0-1 背包，我們再提高一層難度，前面的背包問題，只涉及了背包重量和物品重量，我們現在引入物品價值這一變數，對于一組不同重量、不同價值、不可分割的物品，我們選擇將某些物品裝入背包，在滿足背包最大重量限制的前提下，背包中可裝入物品的總價值最大是多少呢？

這個問題依舊可以用回溯演算法來解決，這個問題并不復雜，和前面是一樣的，我直接貼出代碼，

	private int maxValue = Integer.MIN_VALUE;
	private int[] weights = {2, 2, 4, 6, 3}; //物品重量
	private int[] value = {3, 4, 8, 9, 6}; //物品價格
	private int num = 5; //物品個數
	private int weight = 9; //背包承受的最大重量
	private boolean[][] mem = new boolean[5][10]; //備忘錄，默認值為false

	public ZeroOneBackpack() {}
	
	public void findSolve(int i, int cw, int cv) {
		if (cw == weight || i == num) {
			if (cv > maxValue) {
				maxValue = cv;
			}
			return;
		}
		findSolve(i + 1, cw, cv);
		if (cw + weights[i] <= weight) {
			findSolve(i + 1, cw + weights[i], cv + value[i]);
		}
	}

針對上面的代碼，我們還是畫出遞回樹，

在這里插入圖片描述
我們發現，在遞回樹中，有幾個節點的 i 和 cw 是完全相同的，比如 f(2, 2, 4) 和 f(2, 2, 3)，在背包中物品總重量一樣的情況下，f(2, 2, 4) 對應的物品總價值更大，我們可以舍棄 f(2, 2, 3) 這種狀態，只需要沿著 f(2, 2, 4) 這條決策路線繼續往下決策就可以，

也就是說，對于 (i, cw) 相同的不同狀態，那我們只需要保留 cv 值最大的那個，繼續遞回處理，其他狀態不予考慮，

我們還是把整個求解程序分為 n 個階段，每個階段會決策一個物品是否放到背包中，每個階段決策完以后，背包中的物品的總重量以及總價值，會有多種情況，也就是會達到多種不同的狀態，

我們用一個二維陣列 states[n][w+1]，來記錄每層可以達到的不同狀態，不過這里陣列存盤的值不再是 boolean 型別的了，而是當前狀態對應的最大總價值，我們把每一層中 (i, cw) 重復的狀態（節點）合并，只記錄 cv 值最大的那個狀態，然后基于這些狀態來推導下一層的狀態，

我還是將代碼貼出來，大家可以做一個參考，


	/**
	 * 動態規劃求0-1背包中最接近背包承受的最大重量且價格最大的值
	 * @param weights 物品重量
	 * @param value 物品價格
	 * @param num 物品數量
	 * @param weight 背包能承受的最大重量
	 * @return 找到的最接近背包最大重量中的價值最高的值
	 */
	public int findSolve(int[] weights, int[] value, int num, int weight) {
		int[][] states = new int[num][weight+1];
		for (int i = 0; i < num; i++) {
			for (int j = 0; j < weight+1; j++) {
				states[i][j] = -1;
			}
		}
		states[0][0] = 0;
		if (weights[0] <= weight) {
			states[0][weights[0]] = value[0];
		}
		for (int i = 1; i < num; i++) { //動態規劃，狀態轉移
			for (int j = 0; j <= weight; j++) { //不選擇第i個物品
				if (states[i-1][j] >= 0) {
					states[i][j] = states[i-1][j];
				}
			}
			for (int j = 0; j <= weight-weights[i]; j++) { //選擇第i個物品
				if (states[i-1][j] > 0) {
					int v = states[i-1][j] + value[i];
					if (v > states[i][j+weights[i]]) {
						states[i][j+weights[i]] = v;
					}
				}
			}
		}
		//找到最大值
		int maxValue = -1;
		for (int j = 0; j <= weight; j++) {
			if (states[num-1][j] > maxValue) {
				maxValue = states[num-1][j];
			}
		}
		return maxValue;
	}

關于這個例子的時間空間復雜度和前面的例子分析方法是一樣的，我不再贅述，直接給出結論，這個例子的時間復雜度和空間復雜度都是 O(n*w)，

Ⅳ 如何利用動態規劃來湊滿減

在看完前面的內容后，相信你對這個問題已經有了自己的思路了，這個問題其實和前面舉的例子都有異曲同工之妙，

解決這個問題我們當然可以用回溯演算法，窮舉所有的排列組合，看大于等于 200 的組合是哪一個，但是，這樣效率也太低了，時間復雜度非常高，是指數級的，當 n 很大的時候，可能雙十一都結束了，你的代碼還沒有運行出結果，那就在女朋友面前太沒有面子了，

所以，我們還是可以將這個問題理解成基礎的 0-1 背包問題，只是將重量換成了價格，然后用動態規劃解決，

購物車中有 n 個商品，我們針對每個商品都決策是否購買，每次決策之后，對應不同的狀態集合，我們還是用一個二維陣列 states[n][x]，來記錄每次決策之后所有可達的狀態，不過，這里的 x 值是多少呢？

0-1 背包問題中，我們找的是小于等于 w 的最大值，x 就是背包的最大承載重量 w + 1，對于這個問題來說，我們要找的是大于等于 200（滿減條件）的值中的最小的，所以就不能設定為 200 加 1 了，就這個實際問題而言，如果要購買的物品的總價格超過 200 太多，比如 1000，那這個羊毛薅得就沒有什么意義了，所以，我們可以限定 x 值為 1001，

不過，這個問題不僅要求大于等于 200 的總價格中的最小的，我們還要找出這個最小總價格對應都要買哪些商品，實際上，我們可以利用 states 陣列，倒推出這個被選擇的商品序列，

我們按照這個思路來寫代碼👇

package com.tyz.first.core;

/**
 * 用動態規劃湊滿減
 * @author Tong
 */
public class Double11Advance {

	public Double11Advance() {
	}
	
	/**
	 * 決策要購買的商品以達到湊滿減而且花錢最少
	 * @param items 商品價格
	 * @param num 商品數量
	 * @param limit 滿減條件
	 */
	public static void double11Advance(int[] items, int num, int limit) {
		boolean[][] states = new boolean[num][3*limit+1];
		states[0][0] = true;
		if (items[0] <= 3*limit+1) {
			states[0][items[0]] = true;
		}
		for (int i = 1; i < num; i++) { //動態規劃
			for (int j = 0; j <= 3*limit; j++) { //不購買第i個商品
				if (states[i-1][j] == true) {
					states[i][j] = states[i-1][j];
				}
			}
			for (int j = 0; j <= 3*limit-items[i]; j++) { //購買第i個商品
				if (states[i-1][j] == true) {
					states[i][j+items[i]] = true;
				}
			}
		}
		int k;
		for (k = limit; k < 3*limit+1; k++) {
			if (states[num-1][k] == true) {
				break; //找到大于等于limit的最小值，即滿足滿家條件的最小金額
			}
		}
		if (k == 3*limit+1) {
			return; //沒有可行解
		}
		System.out.print("購買價格為 ");
		for (int i = num-1; i >= 1; i--) {
			if (k-items[i] >= 0 && states[i-1][k-items[i]] == true) {
				System.out.print(items[i] + " "); //購買這個商品
				k = k - items[i];
			}
		}
		System.out.println("的商品");
		if (k != 0) {
			System.out.println(items[0]);
		}
	}

}

這里的前半部分經過前面幾個例子想必已經很好理解了，我們著重看一下后半部分，看是如何列印出選擇購買哪些商品的，

狀態 (i, j) 只有可能從 (i-1, j) 或者 (i-1, j-value[i]) 兩個狀態是否是可達的，也就是 states[i-1][j] 或者 states[i-1][j-value[i]]是否為 true，

如果states[i-1][j] 可達，就說明我們沒有選擇購買第 i 個商品，如果 states[i-1][j-value[i]] 可達，那就說明我們選擇了購買第 i 個商品，我們從中選擇一個可達的狀態（如果兩個都可達，就隨便選擇一個），然后，繼續迭代地考察其他商品是否有選擇購買，

測驗代碼如下：

package com.tyz.first.test;

import com.tyz.first.core.Double11Advance;

public class Test {

	public static void main(String[] args) {
		int[] items = {66, 21, 31, 48, 18, 9, 47, 12, 6, 3, 71, 99, 130, 170, 88, 100};
		Double11Advance.double11Advance(items, 16, 300);
	}

}

測驗結果如下👇
在這里插入圖片描述
如果你還要薅羊毛到毛到分，那把每個價格都乘以 10 或者 100 就好，結果是一樣的，

在給女朋友展示了這個程式之后，她表示不滿意，要讓我顯示三組，那我就再改一下，我們可以顯示前三名最優的組合，給女朋友一個選擇的機會，

package com.tyz.first.core;

/**
 * 用動態規劃湊滿減
 * @author Tong
 */
public class Double11Advance {

	public Double11Advance() {
	}
	
	/**
	 * 決策要購買的商品以達到湊滿減而且花錢最少
	 * @param items 商品價格
	 * @param num 商品數量
	 * @param limit 滿減條件
	 */
	public static void double11Advance(int[] items, int num, int limit) {
		boolean[][] states = new boolean[num][3*limit+1];
		states[0][0] = true;
		if (items[0] <= 3*limit+1) {
			states[0][items[0]] = true;
		}
		for (int i = 1; i < num; i++) { //動態規劃
			for (int j = 0; j <= 3*limit; j++) { //不購買第i個商品
				if (states[i-1][j] == true) {
					states[i][j] = states[i-1][j];
				}
			}
			for (int j = 0; j <= 3*limit-items[i]; j++) { //購買第i個商品
				if (states[i-1][j] == true) {
					states[i][j+items[i]] = true;
				}
			}
		}
		
		int[] index = new int[3];
		for (int i = 0; i < index.length; i++) {
			index[i] = -1;
		}
		
		int k;
		int j = 0;
		for (k = limit; k < 3*limit+1; k++) {
			if (states[num-1][k] == true) {
				if (index[index.length-1] != -1) {
					break;
				}
				index[j++] = k;
				continue; //找到大于等于limit的最小值，即滿足滿家條件的最小金額
			}
		}
		if (k == 3*limit+1) {
			return; //沒有可行解
		}
		System.out.print("最優購買價格為 ");
		for (int i = num-1; i >= 1; i--) {
			if (index[0]-items[i] >= 0 && states[i-1][index[0]-items[i]] == true) {
				System.out.print(items[i] + " "); //購買這個商品
				index[0] = index[0] - items[i];
			}
		}
		if (index[0] != 0) {
			System.out.println(items[0]);
		}
		System.out.println("的商品");
		
		System.out.print("次優購買價格為 ");
		for (int i = num-1; i >= 1; i--) {
			if (index[1]-items[i] >= 0 && states[i-1][index[1]-items[i]] == true) {
				System.out.print(items[i] + " "); //購買這個商品
				index[1] = index[1] - items[i];
			}
		}
		if (index[1] != 0) {
			System.out.println(items[0]);
		}
		System.out.println("的商品");
		
		System.out.print("次次優購買價格為 ");
		for (int i = num-1; i >= 1; i--) {
			if (index[2]-items[i] >= 0 && states[i-1][index[2]-items[i]] == true) {
				System.out.print(items[i] + " "); //購買這個商品
				index[2] = index[2] - items[i];
			}
		}
		if (index[2] != 0) {
			System.out.println(items[0]);
		}
		System.out.println("的商品");
	}

}

測驗代碼運行結果如下👇
在這里插入圖片描述
關于動態規劃更進一步的內容，可以跳轉去看我下面的文章👇

【資料結構與演算法】-＞演算法-＞動態規劃（中）-＞詳解動態規劃理論

【資料結構與演算法】-＞演算法-＞動態規劃（下）-＞如何實作搜索引擎的拼寫糾錯功能？

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/76266.html

標籤：其他

上一篇：2020-09-17

下一篇：深度學習環境搭建