動態(tài)規(guī)劃
動態(tài)規(guī)劃法的求解過程：
- 劃分子問題：將原問題分解為若干個子問題镀岛，每個子問題對應一個決策階段，并且子問題之間具有重疊關系衩侥。
- 確定動態(tài)規(guī)劃函數：根據子問題之間的重疊關系找到子問題滿足的遞推關系式(即動態(tài)規(guī)劃函數)茫藏，這是動態(tài)規(guī)劃法的關鍵民鼓。
- 填寫表格：設計表格薇芝，以自底向上的方式計算各個子問題的解并填表，實現動態(tài)規(guī)劃過程丰嘉。
動態(tài)規(guī)劃算法的基本要素為最優(yōu)子結構性質與子問題重疊性質恩掷。
當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結構性質供嚎，也稱此問題滿足最優(yōu)性原理黄娘。
子問題重疊性質是指在用遞歸算法自頂向下對問題進行求解時峭状，每次產生的子問題并不總是新問題，有些子問題會被重復計算多次逼争。
背包問題
背包問題是一種組合優(yōu)化的NP完全問題优床。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格誓焦，在限定的總重量內胆敞，如何選擇，才能使得物品的總價格最高杂伟。
三種背包：
- 01背包：物品只可以取一次
- 完全背包：物品可以取無限次
- 多重背包：物品可以取的次數有一個上限
01背包：設表示將n個物品裝入容量為C的背包獲得的最大價值移层，顯然，初始子問題是把前面i個物品裝入容量為0的背包和把0個物品裝入容量為j的背包赫粥，得到的價值均為0观话，即：
。
在在決策
時越平，已確定了
频蛔，則問題處于下列兩種狀態(tài)之一：
背包容量不足以裝入物品i，則裝入前i個物品得到的最大價值和裝入前i-1個物品得到的最大價值是相同的秦叛，即
晦溪，背包不增加價值。
背包容量可以裝入物品i挣跋，如果把第i個物品裝入背包三圆，則背包中物品的價值等于把前i-1個物品裝入容量為
的背包中的價值加上第i個物品的價值v；如果第i個物品沒有裝入背包避咆，則背包中物品的價值等于把前i-1個物品裝入容量為j的背包中所取得的價值舟肉。顯然，取二者中價值較大者作為把前i個物品裝入容量為j的背包中的最優(yōu)解牌借。則得到如下遞推式：
從的值向前推度气，如果
割按，表明第n個物品被裝入背包膨报，前n-1個物品被裝入容量為
的背包中。
import java.util.Arrays;
public class DynamicProgramming {
// 動態(tài)規(guī)劃解決01背包
public static int knapsack01(int[] weight, int[] value, int n, int capacity) {
// 表格的行代表物品适荣，列代表容量
int[][] table = new int[n + 1][capacity + 1];
// 初始化表格的第0列
for (int c = 0; c <= n; c++)
table[c][0] = 0;
// 初始化表格的第0行
for (int r = 0; r <= capacity; r++)
table[0][r] = 0;
// 填寫表格
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= capacity; j++)
if (j < weight[i]) // 此時的容量j现柠，裝不下物品i
// 此時價值為上一行這個容量時的價值
table[i][j] = table[i - 1][j];
else // 此時的容量j，能裝下物品i
table[i][j] = Math.max(table[i - 1][j], table[i - 1][j - weight[i]] + value[i]);
}
// 裝入背包的物品：0未裝入弛矛，1裝入
int[] loaded = new int[n + 1];
for (int i = n, j = capacity; i > 0; i--)
if (table[i][j] > table[i - 1][j]) {
loaded[i] = 1;
j = j - weight[i];
} else {
loaded[i] = 0;
}
System.out.println(Arrays.toString(loaded));
return table[n][capacity];
}
public static void main(String[] args) {
// 商品編號從1開始
int[] weight = {0, 2, 12, 1, 1, 4};
int[] value = {0, 2, 4, 2, 1, 10};
// 物品數量
int n = weight.length - 1;
int capacity = 15;
// [0, 1, 0, 1, 1, 1]
// 15
System.out.println(knapsack01(weight, value, n, capacity));
}
}
