序：
工作快七個(gè)年頭了儒陨，現(xiàn)在寫起算法來很是吃力，頭腦生銹得很是厲害笋籽”哪可想而知，平時(shí)寫的代碼質(zhì)量是有多差车海〉言埃看來基本功得不斷打磨練習(xí)隘击。
背包題目：
有n個(gè)物品，每個(gè)物品具有重量和價(jià)值兩個(gè)屬性⊙忻現(xiàn)有一背包最多能裝重量w埋同，求出價(jià)值最大的物品選擇方案。
練習(xí)題目如圖：
image.png
用動(dòng)態(tài)規(guī)劃思維分析
動(dòng)態(tài)規(guī)劃核心三要素：最優(yōu)子結(jié)構(gòu)棵红，邊界凶赁，狀態(tài)轉(zhuǎn)移公式。
最優(yōu)子結(jié)構(gòu)：每個(gè)物品有兩個(gè)狀態(tài)逆甜，被裝或不被裝虱肄。所以被分解程如下兩個(gè)子結(jié)構(gòu)
image.png
邊界：當(dāng)n為1時(shí)，若物品重量小于背包w交煞，則允許物品被裝咏窿。若物品重量大于背包w，則不允許被裝素征。
狀態(tài)轉(zhuǎn)移公式（用i表示物品重量數(shù)組）：
f(n,w) = 0集嵌；（n<1)或（n==1且i[0] > w）
f(n,w) = i[0]；(n==1且i[0] < w)
f(n,w) = f(n-1, w)御毅；（n>1且i[n-1] > w）
f(n,w)= max(f(n-1,w)根欧，f(n-1,w-i[n-1]) + i[n-1]))；（n>1且i[n-1] < w）
遞歸求解
算法思想：自頂向下亚享，有重復(fù)計(jì)算咽块。
求解過程如下圖：
image.png
import java.text.SimpleDateFormat;
import java.util.Date;
/**
* 背包算法
* 題目：有n個(gè)物品，每個(gè)物品具有重量和價(jià)值兩個(gè)屬性∑鬯埃現(xiàn)有一背包最多能裝重量w侈沪，求出價(jià)值最大的物品選擇方案。
*/
public class KnapsackAlgorithm {
/**
* 物品類
*/
private static class Item {
// 重量
private int weight;
// 價(jià)值
private int value;
public Item(int weight, int value) {
this.weight = weight;
this.value = value;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
public static void main(String[] args) {
int knapsackSize = 8;
// 初始化4個(gè)物品
Item[] items = new Item[4];
items[0] = new Item(2, 3);
items[1] = new Item(3, 4);
items[2] = new Item(4, 5);
items[3] = new Item(6, 6);
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd hh:mm:ss");
KnapsackAlgorithm knapsackAlgorithm = new KnapsackAlgorithm();
System.out.println("current time:" + simpleDateFormat.format(new Date()));
ResultNode resultNode = knapsackAlgorithm.getMostValuableWays_recursion(knapsackSize, items, items.length);
System.out.println("max value:" + resultNode.getSumValue());
System.out.println("current time:" + simpleDateFormat.format(new Date()));
}
private static class ResultNode {
private int index;
private int sumValue;
private int sumWeight;
private ResultNode left;
private ResultNode right;
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public int getSumValue() {
return sumValue;
}
public void setSumValue(int sumValue) {
this.sumValue = sumValue;
}
public ResultNode getLeft() {
return left;
}
public void setLeft(ResultNode left) {
this.left = left;
}
public ResultNode getRight() {
return right;
}
public void setRight(ResultNode right) {
this.right = right;
}
public int getSumWeight() {
return sumWeight;
}
public void setSumWeight(int sumWeight) {
this.sumWeight = sumWeight;
}
}
/**
* 遞歸求解
* @return
*/
private ResultNode getMostValuableWays_recursion(int knapsackSize, Item[] items, int n) {
if (n == 1) {
if (items[n-1].getWeight() <= knapsackSize) {
ResultNode resultNode = new ResultNode();
resultNode.setIndex(n-1);
resultNode.setLeft(null);
resultNode.setRight(null);
resultNode.setSumValue(items[n-1].getValue());
resultNode.setSumWeight(items[n-1].getWeight());
return resultNode;
} else {
return null;
}
} else if (n < 1) {
return null;
}
if (items[n-1].getWeight() > knapsackSize) {
return getMostValuableWays_recursion(knapsackSize, items, n-1);
} else {
ResultNode leftNode = getMostValuableWays_recursion(knapsackSize, items, n-1);
if (leftNode != null && leftNode.getSumWeight() > knapsackSize) {
leftNode = null;
}
ResultNode node = getMostValuableWays_recursion(knapsackSize - items[n-1].getWeight(), items, n-1);
ResultNode rightNode = new ResultNode();
rightNode.setIndex(n-1);
rightNode.setRight(node);
rightNode.setSumValue(node != null ? node.getSumValue() + items[n - 1].getValue() : items[n - 1].getValue());
rightNode.setSumWeight(node != null ? node.getSumWeight() + items[n - 1].getWeight() : items[n - 1].getWeight());
if (rightNode.getSumWeight() > knapsackSize) {
rightNode = null;
}
if (leftNode != null && rightNode != null) {
if (leftNode.getSumValue() > rightNode.getSumValue()) {
return leftNode;
} else if (leftNode.getSumValue() < rightNode.getSumValue()) {
return rightNode;
} else {
ResultNode resultNode = new ResultNode();
resultNode.setIndex(-1);
resultNode.setLeft(leftNode);
resultNode.setRight(rightNode);
resultNode.setSumValue(leftNode.getSumValue());
return resultNode;
}
} else if (leftNode != null){
return leftNode;
} else if (rightNode != null) {
return rightNode;
} else {
return null;
}
}
}
}
注意：getMostValuableWays_recursion中的條件分支正好與狀態(tài)轉(zhuǎn)移公式的條件對(duì)應(yīng)晚凿。
備忘錄求解
算法思想：自頂向下亭罪，無重復(fù)計(jì)算。
此算法也是利用遞歸求解歼秽，與遞歸求解的區(qū)別在于運(yùn)用了新的數(shù)據(jù)結(jié)構(gòu)（比如map）來緩存算過的值应役。
/**
* 備忘錄求解
*/
private ResultNode getMostValuableWays_memo(int knapsackSize, Item[] items, int n, KnapsackMap map) {
if (n == 1) {
if (items[n-1].getWeight() <= knapsackSize) {
ResultNode resultNode = new ResultNode();
resultNode.setIndex(n-1);
resultNode.setLeft(null);
resultNode.setRight(null);
resultNode.setSumValue(items[n-1].getValue());
resultNode.setSumWeight(items[n-1].getWeight());
return resultNode;
} else {
return null;
}
} else if (n < 1) {
return null;
}
if (items[n-1].getWeight() > knapsackSize) {
if (!map.containsKey(n-1, knapsackSize)) {
map.put(n-1, knapsackSize, getMostValuableWays_memo(knapsackSize, items, n-1, map));
}
return map.get(n-1, knapsackSize);
} else {
if (!map.containsKey(n-1, knapsackSize)) {
map.put(n-1, knapsackSize, getMostValuableWays_memo(knapsackSize, items, n-1, map));
}
ResultNode leftNode = map.get(n-1, knapsackSize);
if (leftNode != null && leftNode.getSumWeight() > knapsackSize) {
leftNode = null;
}
if (!map.containsKey(n-1, knapsackSize - items[n-1].getWeight())) {
map.put(n-1, knapsackSize - items[n-1].getWeight(), getMostValuableWays_memo(knapsackSize - items[n-1].getWeight(), items, n-1, map));
}
ResultNode node = map.get(n-1, knapsackSize - items[n-1].getWeight());
ResultNode rightNode = new ResultNode();
rightNode.setIndex(n-1);
rightNode.setRight(node);
rightNode.setSumValue(node != null ? node.getSumValue() + items[n - 1].getValue() : items[n - 1].getValue());
rightNode.setSumWeight(node != null ? node.getSumWeight() + items[n - 1].getWeight() : items[n - 1].getWeight());
if (rightNode.getSumWeight() > knapsackSize) {
rightNode = null;
}
if (leftNode != null && rightNode != null) {
if (leftNode.getSumValue() > rightNode.getSumValue()) {
return leftNode;
} else if (leftNode.getSumValue() < rightNode.getSumValue()) {
return rightNode;
} else {
ResultNode resultNode = new ResultNode();
resultNode.setIndex(-1);
resultNode.setLeft(leftNode);
resultNode.setRight(rightNode);
resultNode.setSumValue(leftNode.getSumValue());
return resultNode;
}
} else if (leftNode != null){
return leftNode;
} else if (rightNode != null) {
return rightNode;
} else {
return null;
}
}
}
private static class Knapsack {
private int num;
private int weidht;
public int getNum() {
return num;
}
public void setNum(int num) {
this.num = num;
}
public int getWeidht() {
return weidht;
}
public void setWeidht(int weidht) {
this.weidht = weidht;
}
@Override
public int hashCode() {
return 2;
}
@Override
public boolean equals(Object obj) {
Knapsack objLocal = (Knapsack)obj;
return num == objLocal.getNum() && weidht == objLocal.getWeidht();
}
}
private static class KnapsackMap extends HashMap<Knapsack, ResultNode> {
public boolean containsKey(int num, int knapsack) {
Knapsack knapsack1 = new Knapsack();
knapsack1.setNum(num);
knapsack1.setWeidht(knapsack);
return super.containsKey(knapsack1);
}
public ResultNode get(int num, int knapsack) {
Knapsack knapsack1 = new Knapsack();
knapsack1.setNum(num);
knapsack1.setWeidht(knapsack);
return super.get(knapsack1);
}
public ResultNode put(int num, int knapsack, ResultNode value) {
Knapsack knapsack1 = new Knapsack();
knapsack1.setNum(num);
knapsack1.setWeidht(knapsack);
return super.put(knapsack1, value);
}
}
動(dòng)態(tài)規(guī)劃求解
算法思想：采用由低向上的思維方式，即從1個(gè)物品開始求解燥筷，直到n個(gè)物品箩祥。
求解過程：
第一步：
| 1kg | 2kg | 3kg | 4kg | 5kg | 6kg | 7kg | 8kg |
|---|---|---|---|---|---|---|---|
| 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
說明：背包能裝8千克，所以表格分成8列肆氓。行數(shù)代表物品的規(guī)模袍祖。
單元格值即為f(n,w)，n為物品數(shù)谢揪。若n為1蕉陋，就包含第一個(gè)物品（w:2kg, v3$）捐凭；n為2，就包含第一個(gè)和第二個(gè)物品（w:2kg,v:3$和w:3kg,v:4$）凳鬓；以此類推茁肠。
第二步：
| 列1 | 列2 | 列3 | 列4 | 列5 | 列6 | 列7 | 列8 |
|---|---|---|---|---|---|---|---|
| 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 0 | 3 | 4 | 4 | 7 | 7 | 7 | 7 |
第三步：
| 列1 | 列2 | 列3 | 列4 | 列5 | 列6 | 列7 | 列8 |
|---|---|---|---|---|---|---|---|
| 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 0 | 3 | 4 | 4 | 7 | 7 | 7 | 7 |
| 0 | 3 | 4 | 5 | 5 | 8 | 9 | 9 |
第四步：
| 列1 | 列2 | 列3 | 列4 | 列5 | 列6 | 列7 | 列8 |
|---|---|---|---|---|---|---|---|
| 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 0 | 3 | 4 | 4 | 7 | 7 | 7 | 7 |
| 0 | 3 | 4 | 5 | 5 | 8 | 9 | 9 |
| 0 | 3 | 4 | 5 | 5 | 8 | 9 | 9 |
注意：f(4,8)=第4行8列單元格值。
/**
* 動(dòng)態(tài)規(guī)劃求解
*/
private int getMostValuableWays_dynamicPrograming(int knapsackSize, Item[] items, int n) {
int[] preResult = null;
int[] result = new int[knapsackSize];
for(int i = 1; i <= n; i++) {
for(int w = 1; w <= knapsackSize; w++) {
if (i == 1) {
if (items[i-1].getWeight() > w) {
result[w-1] = 0;
} else {
result[w-1] = items[i-1].getValue();
}
} else {
if (w-items[i-1].getWeight()-1 >=0) {
if (preResult[w-1] > preResult[w-items[i-1].getWeight()-1] + items[i-1].getValue()) {
result[w-1] = preResult[w-1];
} else {
result[w-1] = preResult[w-items[i-1].getWeight()-1] + items[i-1].getValue();
}
} else if (w-items[i-1].getWeight() == 0) {
result[w-1] = items[i-1].getValue();
} else {
result[w-1] = 0;
}
}
}
preResult = Arrays.copyOf(result, 8);
}
return result[knapsackSize-1];
}
算法時(shí)間復(fù)雜度和空間復(fù)雜度分析
遞歸:
時(shí)間復(fù)雜度：O(2^n)缩举，隨物品數(shù)改變垦梆。
空間復(fù)雜度：O(2^n)
備忘錄:
時(shí)間復(fù)雜度：O(2^n)，隨物品數(shù)改變蚁孔。
空間復(fù)雜度：O(2^n)
動(dòng)態(tài)規(guī)劃:
時(shí)間復(fù)雜度：O(n^w)奶赔，隨物品數(shù)和背包重量改變惋嚎。
空間復(fù)雜度：O(w)
