序：
工作快七个年头了，现在写起算法来很是吃力，头脑生锈得很是厉害。可想而知，平时写的代码质量是有多差。看来基本功得不断打磨练习。
背包题目：
有n个物品，每个物品具有重量和价值两个属性。现有一背包最多能装重量w，求出价值最大的物品选择方案。
练习题目如图：
image.png
用动态规划思维分析
动态规划核心三要素：最优子结构，边界，状态转移公式。
最优子结构：每个物品有两个状态，被装或不被装。所以被分解程如下两个子结构
image.png
边界：当n为1时，若物品重量小于背包w，则允许物品被装。若物品重量大于背包w，则不允许被装。
状态转移公式（用i表示物品重量数组）：
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）
递归求解
算法思想：自顶向下，有重复计算。
求解过程如下图：
image.png
import java.text.SimpleDateFormat;
import java.util.Date;
/**
* 背包算法
* 题目：有n个物品，每个物品具有重量和价值两个属性。现有一背包最多能装重量w，求出价值最大的物品选择方案。
*/
public class KnapsackAlgorithm {
/**
* 物品类
*/
private static class Item {
// 重量
private int weight;
// 价值
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个物品
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中的条件分支正好与状态转移公式的条件对应。
备忘录求解
算法思想：自顶向下，无重复计算。
此算法也是利用递归求解，与递归求解的区别在于运用了新的数据结构（比如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);
}
}
动态规划求解
算法思想：采用由低向上的思维方式，即从1个物品开始求解，直到n个物品。
求解过程：
第一步：
| 1kg | 2kg | 3kg | 4kg | 5kg | 6kg | 7kg | 8kg |
|---|---|---|---|---|---|---|---|
| 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
说明：背包能装8千克，所以表格分成8列。行数代表物品的规模。
单元格值即为f(n,w)，n为物品数。若n为1，就包含第一个物品（w:2kg, v3$）；n为2，就包含第一个和第二个物品（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列单元格值。
/**
* 动态规划求解
*/
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];
}
算法时间复杂度和空间复杂度分析
递归:
时间复杂度：O(2^n)，随物品数改变。
空间复杂度：O(2^n)
备忘录:
时间复杂度：O(2^n)，随物品数改变。
空间复杂度：O(2^n)
动态规划:
时间复杂度：O(n^w)，随物品数和背包重量改变。
空间复杂度：O(w)
