一個簡單的0-1背包問題；規定背包的最大容量是4公斤；並且放入背包的物品不能重複，怎麼樣讓背包的物品價值量最大化？
| 物品 | 重量 | 價值 |
| 吉他(G) | 1 | 1500 |
| 音響(S) | 4 | 3000 |
| 筆記型電腦(L) | 3 | 2000 |
動態規劃算法的思想也是將復雜問題規劃分解為小問題，但是和分治算法不同的地方是，
動態規劃算法分解得到的子問題有遞進關係；子問題的最優解會成為最終的解；
可以這麼看；分解得到的子問題的求解是建立在上一個階段子問題的求解基礎上；這些子問題不是相互獨立的。
package utitled;
public class DynamicProgrammingDemo {
public static void main(String[] args) {
// 背包的容量
int capacity = 4;
// 商品價值(依序)：吉他(G),音響(S),筆記型電腦(L)
int[] values = {1500, 3000, 2000};
// 商品重量(依序)：吉他(G),音響(S),筆記型電腦(L)
int[] weights = {1, 4, 3};
// 背包放入最佳價值額
int[][] bestValues = new int[values.length + 1][capacity + 1];
// 保存 當前商品價值 + 背包剩餘容量空間價值的二維陣列座標
int[][] traces = new int[values.length + 1][capacity + 1];
for (int i = 1; i < bestValues.length; i++) {
for (int j = 1; j < bestValues[i].length; j++) {
// 若背包放不下
if (j < weights[i-1]) {
bestValues[i][j] = bestValues[i-1][j];
} else if (values[i-1] + bestValues[i-1][j-weights[i-1]] > bestValues[i-1][j]) {
// 背包放的下
bestValues[i][j] =
// 當前商品價值 + 背包剩餘容量空間價值
values[i-1] + bestValues[i-1][j-weights[i-1]];
// 紀錄trace
traces[i][j] = 1;
} else {
// 背包放的下(當前商品價值 + 背包剩餘容量空間價值 < bestValues[i-1][j])
bestValues[i][j] = bestValues[i-1][j];
}
}
}
// 輸出背包個容量最佳價值額(capacity 1~4)
for (int i = 0; i < bestValues.length; i++) {
for (int j = 0; j < bestValues[i].length; j++) {
System.out.print(bestValues[i][j] + "\t");
}
System.out.println();
}
for (int i = 0; i < traces.length; i++) {
for (int j = 0; j < traces[i].length; j++) {
System.out.print(traces[i][j] + "\t");
}
System.out.println();
}
int i = traces.length - 1;
int j = 4;
while (i > 0 && j > 0) {
if (traces[i][j] == 1) {
System.out.printf("將第%d商品放入背包，價值%d\n", i, values[i-1]);
j -= weights[i-1];
}
i--;
}
}
}
如有敘述錯誤，還請不吝嗇留言指教，thanks!
