1背包問題
```java
package net.zhaoxuyang.common.algorithm.dp;
import java.util.Arrays;
/**
* 0-1 背包問題
*
* <pre>
* n個物品和1個背包,對物品i,價值為v[i],重量為w[i],背包容量為W,如何裝入使得總價值最大:
* - w[i]x[i]小于等于W
* - x[i]∈{0,1}
* - 目標函數為max(v[i]x[i])
* - 其中i∈[1,n]
*
* 假如(x[1], x[2], x[3], ..., x[n])是最優解,
* 那么(x[2], x[3], ..., x[n])則是以下問題的一個最優解:
* - w[i]x[i] 小于等于 W - w[1]x[1]
* - x[i]∈{0,1}
* - 目標函數為max(v[i]x[i])
* - 其中i∈[2,n]
*
* </pre>
*
* 時間復雜度為O(nW)
* 缺點:要求w數組中的元素為整數;當W>2^n時,時間復雜度為O(n2^n)
* @author zhaoxuyang
*/
public class KnapSack {
public static void main(String[] args) {
int[] w = {2, 2, 6, 5, 4};
int[] v = {6, 3, 5, 4, 6};
int W = 10;
byte[] result = fun(w, v, W);
System.out.println(Arrays.toString(result));
}
/**
*
* <pre>
* 數組c[w.length+1][W+1]存放每次迭代的執行結果
* 數組x[w.length]存放所裝入的背包的物品狀態
* @初始化 c[0][j] = c[i][0] = 0
*
* @遞歸式 c[i][j] = c[i-1][j] j 小于 w[i]
* = max{c[i-1][j],c[i-1][j-w[i]]+v[i]} j大于等于w[i]
* </pre>
* @param w 重量
* @param v 價值
* @param W 容量
* @return 最優解
*/
private static byte[] fun(int[] w, int[] v, int W) {
int row = w.length;
int col = W;
byte[] x = new byte[row];
int[][] c = new int[row + 1][col + 1];
//存放各個子問題的最優值
for (int i = 1; i <= row; i++) {
for (int j = 1; j <= col; j++) {
if (j < w[i - 1]) {
c[i][j] = c[i - 1][j];
} else {
int tmp = c[i - 1][j - w[i - 1]] + v[i - 1];
c[i][j] = Math.max(c[i - 1][j], tmp);
}
}
}
//構造最優解
for (int i = row, j = col; i > 0; i--) {
if (c[i][j] > c[i - 1][j]) {
x[i - 1] = 1;
j -= w[i - 1];
}
}
return x;
}
}
```
- 1 設計接口
- 1.1 容器接口Container
- 1.2 背包接口Bag
- 1.3 棧接口Stack
- 1.4 隊列接口Queue
- 1.5 Union-Find算法接口UF
- 2 實現接口
- 2.1 結點類Node
- 2.2 數組迭代器ArrayIterator
- 2.3 鏈表迭代器ListIterator
- 2.4 背包(Bag)的實現
- 2.4.1 能動態調整數組大小的Bag
- 2.4.2 鏈式Bag的實現
- 2.5 棧(Stack)的實現
- 2.5.1 能動態調整數組大小的Stack
- 2.5.2 鏈式Stack的實現
- 2.6 隊列(Queue)的實現
- 2.6.1 能動態調整數組大小的Queue
- 2.6.2 鏈式Queue的實現
- 2.7 Union-Find算法的實現
- 2.7.1 DefaultUF
- 2.7.2 QuickFindUF
- 2.7.3 QuickUnionUF
- 2.7.4 WeightedQuickUnionUF
- 2.8 測試
- 2.8.1 測試Stack
- 2.8.2 測試Union-Find
- 3 排序算法
- 3.1 定義排序工具的類結構
- 3.2 選擇排序
- 3.3 插入排序
- 3.4 希爾排序
- 3.5 歸并排序
- 3.5.1 歸并排序的合并方法
- 3.5.2 自頂向下的歸并排序
- 3.5.3 自底向上的歸并排序
- 3.6 快速排序
- 3.6.1 常規快速排序
- 3.6.2 排序前先洗牌
- 3.6.3 快速排序的改進方法-小數據量轉成插入排序
- 3.6.4 快速排序的改進方法-三向切分
- 3.7 堆排序
- 3.8 最終的排序工具
- 4 搜索
- 4.1 二分搜索(binarySearch)
- 4.2 優先隊列(MaxPriorityQueue)
- 4.3 二叉查找樹(BST)
- 4.4 紅黑二叉查找樹(RedBlackBST)
- 4.5 B-樹(BTree)
- 5 圖
- 5.1 無向圖(Graph)
- 5.2 有向圖(Digraph)
- 6 貪心
- Dijkstra算法-單元最短路徑
- 7 動態規劃
- 7.1 最長公共子序列問題
- 7.2 0-1背包問題
- 7.3 加工順序問題
- 8 搜索法
- 8.1 圖的著色問題
- 8.2 深度優先搜索
- 8.3 回溯法
- 8.3.1 回溯法的算法框架
- 8.3.2 子集樹
- 8.3.3 排列樹
- 8.3.4 滿m叉樹(組合樹)
- 8.4 廣度優先搜索
- 8.5 分支限界法
- 9 隨機化算法
- 9.1 數值隨機化算法
- 9.2 蒙特卡羅算法
- 9.3 拉斯維加斯算法
- 9.4 舍伍德算法
- 10 數論算法
- 10.1 Stein求最大公約數
- 10.2 矩陣求斐波那切數列
- LeetCode刷題筆記