Greedy & Back-track & Branch and Bound
贪心算法 算法+证明
一、最优装载问题 算法： void Loading(int x[], int w[], int c, int n) { int *t = new int [n+1]; Sort(w, t, n); for(int i = 0; i < n; i++) x[i] = 0; for(int i = 0; i < n && w[t[i]] < c; i++) { x[t[i]] = 1; c -= w[t[i]]; } } 证明： 最优子结构性质： 二、哈夫曼编码 三、最小生成树 回溯法 子集树：0-1背包问题，从包含n个全集当中去选择一个子集，所有可能解是$O(2^n)$ 排序树：TSP问题，解是一个排列，所有可能解的规模是$O(n!)$
子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间称为子集树。 遍历子集树 时间复杂度：$O(2^n)$ void backtrack (int t) { if (t>n) output(x); else { for (int i=0;i<=1;i++) { x[t]=i; if (legal(t)) backtrack(t+1); } } } 排列树：当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树成为排列树。 遍历排序树 时间复杂度：$O(n!
