前言
今天開始學(xué)習(xí)動態(tài)規(guī)劃拟逮，一共有三節(jié)撬统，分別是：初識動態(tài)規(guī)劃、動態(tài)規(guī)劃理論敦迄、動態(tài)規(guī)劃實戰(zhàn)恋追。今天這一節(jié)就是初識動態(tài)規(guī)劃。
動態(tài)規(guī)劃比較適合用來求解最優(yōu)問題罚屋，比如最大值苦囱、最小值等等。它可以非常顯著地降低時間復(fù)雜度脾猛，提高代碼的執(zhí)行效率撕彤。
下面會通過兩個非常經(jīng)典的動態(tài)規(guī)劃問題模型來展示為什么需要動態(tài)規(guī)劃，以及動態(tài)規(guī)劃解題方法是如何演化出來的猛拴。
0-1背包問題
對于一組不同重量羹铅、不同分割的物品蚀狰，我們需要選擇一些裝入背包，在滿足背包最大重量限制的前提下职员，背包中物品總重量的最大值是多少呢麻蹋？
這問題可以通過回溯算法來解決，代碼如下：
public class Soluction {
private int maxW = int.MinValue; // 結(jié)果
private int[] weight = new int[] { 2, 2, 4, 6, 3 }; // 物品重量
private int n = 5; // 物品個數(shù)
private int w = 9; // 背包最大承受
public void F (int i, int cw) {
if (cw == w || i == n) { // cw==w表示背包滿了廉邑，i==n表示物品都考察完了
if (cw > maxW) maxW = cw;
return;
}
F (i + 1, cw); // 選擇不裝第i個物品
if (cw + weight[i] <= w) {
F (i + 1, cw + weight[i]); // 選擇裝第i個物品
}
}
public int GetResult () {
return maxW;
}
}
回溯算法可以通過遞歸樹來分析哥蔚，如下圖：
通過遞歸樹可計算回溯算法的時間復(fù)雜度，時間復(fù)雜度是指數(shù)級的蛛蒙，非常高糙箍。
通過遞歸樹可知，回溯算法中存在大量的重復(fù)計算牵祟，這個可以通過“備忘錄”的方法來優(yōu)化深夯，優(yōu)化后的代碼如下：
// 回溯算法優(yōu)化，增加“備忘錄”
public class Soluction2 {
private int maxW = int.MinValue; // 結(jié)果
private int[] weight = new int[] { 2, 2, 4, 6, 3 }; // 物品重量
private int n = 5; // 物品個數(shù)
private int w = 9; // 背包最大承受
private bool[][] mem = new bool[5][]; // 備忘錄诺苹，默認(rèn)值false
public Soluction2 () {
for (int i = 0; i < 5; i++) {
mem[i] = new bool[10];
}
}
public void F (int i, int cw) {
if (cw == w || i == n) { // cw==w表示背包滿了咕晋，i==n表示物品都考察完了
if (cw > maxW) maxW = cw;
return;
}
if (mem[i][cw]) return; // 重復(fù)狀態(tài)
F (i + 1, cw); // 選擇不裝第i個物品
if (cw + weight[i] <= w) {
F (i + 1, cw + weight[i]); // 選擇裝第i個物品
}
}
public int GetResult () {
return maxW;
}
}
下面我們來看一下動態(tài)規(guī)劃是如何解決這個問題的。
- 把整個求解過程分為n個階段收奔，每個階段會決策一個物品是否放到背包中掌呜。
- 把每一層重復(fù)的狀態(tài)合并，只記錄不同的狀態(tài)坪哄，然后基于上一層的狀態(tài)集合來推導(dǎo)下一層的狀態(tài)集合质蕉。
- 以此類推，直到考察完所有物品翩肌。只需要在最后一層模暗，找一個值為true的最接近w的值，就是背包中物品總重量的最大值念祭。
整個過程如下圖：
翻譯成代碼如下：
public int Knapsack (int[] weight, int n, int w) {
bool[][] states = new bool[n][]; // 默認(rèn)值false
for (int i = 0; i < n; i++) states[i] = new bool[w + 1];
states[0][0] = true; // 第一行的數(shù)據(jù)要特殊處理兑宇，可以利用哨兵優(yōu)化
if (weight[0] <= w) states[0][weight[0]] = true;
for (int i = 1; i < n; i++) // 動態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移
{
for (int j = 0; j <= w; j++) // 不把第i個物品放入背包，則把上一輪的狀態(tài)移下來
if (states[i - 1][j]) states[i][j] = states[i - 1][j];
for (int j = 0; j <= w - weight[i]; j++) // 放第i個物品粱坤，在不超出背包最大承重w的范圍內(nèi)隶糕，再判斷上一輪的狀態(tài)，來設(shè)置
if (states[i - 1][j]) states[i][j + weight[i]] = true;
}
for (int i = w; i >= 0; i--) // 從最后一行（下標(biāo)n-1）找到值為true的位置站玄，即為結(jié)果
if (states[n - 1][i]) return i;
return 0;
}
這個代碼的時間復(fù)雜度是O(n * w)枚驻，其中n表示物品個數(shù)，w表示背包可以承載的總重量蜒什〔饨眨空間復(fù)雜度也是O(n * w)，使用了個二維數(shù)組來保存狀態(tài)。
實際上空間復(fù)雜度可以進(jìn)一步代碼霎冯，只需要w + 1的空間即可铃拇。代碼優(yōu)化如下：
public int Knapsack2 (int[] weight, int n, int w) {
bool[] states = new bool[w + 1];
states[0] = true;
if (weight[0] <= w) states[weight[0]] = true;
// 對比上面的代碼，主要是不再保存每一輪的狀態(tài)沈撞，而是合并保存狀態(tài)慷荔。
for (int i = 1; i < n; i++) {
for (int j = w - weight[i]; j >= 0; --j) // 對比上面的代碼，這里是從大到小遍歷缠俺，目的是為了避免狀態(tài)的修改显晶，影響后續(xù)的結(jié)果。
if (states[j]) states[j + weight[i]] = true;
}
for (int i = w; i >= 0; --i)
if (states[i]) return i;
return 0;
}
對比上面的代碼壹士，上面代碼是保存每一輪的狀態(tài)磷雇，而實際上這個問題只需要最后一輪的狀態(tài)即可。但是要注意第8行代碼躏救，j是從大到小遍歷的唯笙，這里主要是因為只有一輪狀態(tài)保存，為了不影響其他狀態(tài)盒使。
0-1背包問題升級版
剛剛的背包只涉及背包重量和物品重量崩掘，我們改造一下剛剛的背包問題，引入物品價值這一變量少办。
對于一組不同重量苞慢、不同價值、不可分割的物品英妓，選擇將某些物品裝入背包挽放，在滿足背包最大重量的限制的前提下，背包中可裝入物品的總價值最大是多少鞋拟？
這個問題依舊可以使用回溯算法來解決骂维，但是就沒辦法通過備忘錄來優(yōu)化了惹资。
我們來看一下動態(tài)規(guī)劃如何解決這個問題贺纲，直接上代碼：
public int Knapsack3 (int[] weight, int[] value, int n, int w) {
int[][] states = new int[n][];
for (int i = 0; i < n; i++) states[i] = new int[w + 1];
states[0][0] = 0;
if (weight[0] <= w) states[0][weight[0]] = value[0];
for (int i = 1; i < n; i++) {
for (int j = 0; j <= w; j++) // 不放第i個物品
if (states[i - 1][j] > 0) states[i][j] = states[i - 1][j];
for (int j = 0; j <= w - weight[i]; j++) // 放第i個物品
if (states[i - 1][j] > 0) states[i][j + weight[i]] = states[i - 1][j] + value[i];
}
for (int i = w; i >= 0; i--) if (states[n - 1][i] > 0) return states[n - 1][i];
return 0;
}
時間復(fù)雜度和空間復(fù)雜度一樣是O(n * w)。同理褪测，一樣可以優(yōu)化空間猴誊，代碼如下：
public int Knapsack4 (int[] weight, int[] value, int n, int w) {
int[] states = new int[w + 1];
states[0] = 0;
if (weight[0] <= w) states[weight[0]] = value[0];
for (int i = 1; i < n; i++) {
for (int j = w - weight[i]; j >= 0; j--) // 放第i個物品
if (states[j] > 0) states[j + weight[i]] = states[j] + value[i];
}
for (int i = w; i >= 0; i--)
if (states[i] > 0) return states[i];
return 0;
}
案例：如何巧妙解決“雙十一”購物時的湊單問題
淘寶的“雙十一”購物節(jié)有各種促銷活動，比如“滿200減50”侮措。假設(shè)你女朋友的購物車中有n個（n>100)想買的商品懈叹，她希望從里面選幾個，在湊夠滿減條件的前提下分扎，讓選出來的商品價格總和最大程度地接近滿減條件（200元）澄成。
直接上代碼：
public class Soluction4 {
// items商品價格，n商品個數(shù), w表示滿減條件，比如200
public void Double11advance (int[] items, int n, int w) {
int[][] states = new int[n][];
for (int i = 0; i < n; i++) {
states[i] = new int[3 * w + 1];
}
states[0][0] = 0;
if (items[0] <= 3 * w) states[0][items[0]] = items[0];
for (int i = 1; i < n; i++) {
for (int j = 0; j <= 3 * w; j++) { // 不放第i個物品
if (states[i - 1][j] > 0) states[i][j] = states[i - 1][j];
}
for (int j = 0; j <= 3 * w - items[i]; j++) { // 放第i個物品
if (states[i - 1][j] > 0) states[i][j + items[i]] = states[i - 1][j] + items[i];
}
}
int maxW = 0; // 找出大于等于w的最小值
for (maxW = w; maxW < 3 * w + 1; ++maxW) {
if (states[n - 1][maxW] > 0) break;
}
if (maxW == 3 * w + 1) return; // 沒有可行解
Console.WriteLine ($"w的最小值：{maxW}");
Console.Write ("購買組合：");
for (int i = n - 1; i >= 1; --i) { // i表示二維數(shù)組中的行墨状，j表示列
if (maxW - items[i] >= 0 && states[i - 1][maxW - items[i]] > 0) { // states[i][j]有值卫漫，要么是不購買i,
Console.Write (items[i] + " "); // 購買這個商品
maxW = maxW - items[i];
}
} // else 沒有購買這個商品，j不變肾砂。
if (maxW != 0) Console.Write (items[0]);
}
}
class Program {
static void Main (string[] args) {
Soluction4 soluction = new Soluction4 ();
soluction.Double11advance (new int[] { 15, 93, 23, 843, 74, 82, 39, 46, 5, 26, 32, 37 }, 12, 200);
}
}
輸出結(jié)果是：37 32 26 5 46 39 15
上面的代碼有一點要注意的列赎，如何根據(jù)狀態(tài)集合來判斷是否購買此商品。
狀態(tài)(i, j)只有可能從(i - 1, j)或者(i - 1, j - value[i])兩個狀態(tài)推導(dǎo)出來镐确。所以就檢查這兩個狀態(tài)是否可達(dá)的包吝，也就是states[i - 1][j]或者states[i - 1][j - value[i]]是否為true。
如果states[i - 1][j]可達(dá)源葫，就說明我們沒有選擇購買第i個商品诗越，如果states[i - 1][j - value[i]]可達(dá)，那就說明我們選擇了購買第i個商品息堂。
