共计 4061 个字符，预计需要花费 11 分钟才能阅读完成。
递归与分治策略
把一个规模为 n 的问题合成为 k 个规模较小的子问题，这些子问题互相独立且与原问题雷同，递归的解这些子问题，而后把各个子问题的解合并失去原问题的解。
【题目】
应用疾速排序办法排列一个一维数组。
【思路】
对于输出的子数组 a[p:r]，依照一下 3 个步骤进行排序：
1）合成 divide：以 a[p] 为基准元素将 a[p:r] 划分成 3 段 a[p:q-1]，a[q] 和 a[q+1:r]，其中 a[q] 不小于 a[p:q-1] 中的任何元素且不大于 a[q+1:r] 中的任何元素，下标 q 在划分中确定。
2）递归求解 conquer：通过递归调用排序，别离对 a[p:q-1] 和 a[q+1:r] 进行排序。
3）合并 merge：合并 a[p:q-1]，a[q] 和 a[q+1:r] 返回为最终后果。
【代码实现】
var __array__ = [1, 3, 2, 4, 5, 57, 6, 46, 4, 6, 45];
console.log("排序前：" + __array__);
function sort(x, y) {if (x < y) {var p = partition(x, y);
sort(x, p - 1);
sort(p + 1, y);
}
}
function partition(p, q) {
var x = p;
var y = q;
var r = p;
var flag = __array__[r];
while (true) {while (__array__[x] <= flag && x < y) {x++;}
while (__array__[y] > flag && y > x) {y--;}
if (x >= y) {break;}
var temp = __array__[x];
__array__[x] = __array__[y];
__array__[y] = temp;
}
if (__array__[x] > flag) {x--;}
__array__[p] = __array__[x];
__array__[x] = flag;
return x;
}
sort(0, __array__.length - 1);
console.log("排序后：" + __array__);动静布局
和分治法根本思维有独特的中央，不同的是子问题往往不是独立的，有事母问题要借助子问题的解来判断，因而把曾经计算好的问题记录在表格中，后续如果须要查问一下，能够防止反复计算，这是动静布局的根本思维。
不过动静布局具体实现起来多种多样，不过都具备雷同的填表格式，通常依照上面步骤设计算法：
1）找出最优解的性质，并刻画其结构特征；
2）递归的定义最优值；
3）以自底向上的形式计算出最优值；
4）通过计算最优值时刻意记录的判断后果来结构最优解。
能够应用该算法思维设计算法的问题个别会具备二个决定性的性质：
1）最优子结构性质；
2）子问题重叠性质。
备忘录算法
和下面的算法思维差不多，不同的是备忘录为每个解过的子问题建设备忘录以备须要的时候查看，防止了雷同的问题计算屡次。
一般来说，当一个问题的所有子问题都至多要解一次时，用动静布局比备忘录要好，因为不会有工作暂存且没有多余的计算；当子问题空间中局部问题不用解时，用备忘录比拟好。
不过下面不是相对的，这样说只是想区别一下二个思维的不同，具体的时候还是要依据业务场景来在保障可行的前提下抉择更好的办法。
【题目】
给定 n 个矩形 {A1,A2,…,An}, 其中 Ai 与 Ai+ 1 是可乘的，因为矩阵满足结合律，不同的加括号办法计算次数不一样，求最优的加括号办法。
【思路】
别离计算有 1，2，3，…，n 个矩阵的最优解，计算 i 个时候，全副的 i - 1 的最优解曾经记录下来了，保障计算不反复。
【代码实现】
/**
* 初始化数据
*/
var P = [30, 35, 15, 5, 10, 20, 25]; // 记录了矩阵的大小
var num = P.length - 1; // 矩阵个数
var minNum = [];
var i, j; // 全局简单循环变量
/**
* 初始化数据
*/
for (i = 0; i < num; i++) {minNum[i] = [];
for (j = 0; j < num; j++) {if (i == j) {minNum[i][j] = 0;
} else {minNum[i][j] = "#";
}
}
}
/**
* 计算最优并记录下来
*/
for(i=2;i<=num;i++){// 计算的矩阵个数，从二个开始到全副的状况
for(j=1;j<=num+1-i;j++){// 计算矩阵第 j 到第 i +j- 1 个的状况
// 先初始化认为在第 j 宰割是最优的（在第 j 宰割的意思是 j 独自一个，j+1->i+j- 1 是一组）var splitIndex=j;
var splitMin=minNum[j][i+j-2]+P[j-1]*P[j]*P[i+j-1];
minNum[j-1][i+j-2]=splitMin;
for(splitIndex=j+1;splitIndex<=i+j-2;splitIndex++){splitMin=minNum[j-1][splitIndex-1]+minNum[splitIndex][i+j-2]+P[j-1]*P[splitIndex]*P[i+j-1];
if(splitMin<minNum[j-1][i+j-2]){minNum[j-1][i+j-2]=splitMin;
}
}
}
}
console.log("最优次数:");
console.log(minNum);贪婪算法
算法思维很简略，和字面意思一样，每次都抉择对本人最无利的，不过这是有条件的，只有在满足条件下每次抉择最无利本人的才能够获取最优解。
贪婪抉择性质和最优子结构性质是该思维最重要的性质：
1）贪婪抉择性质：所求问题的整体最优解能够通过一系列部分最优的抉择达到。
2）最优子结构性质：当一个问题的最优解蕴含其子问题的最优解时，称此问题具备此性质。
【题目】
有一批集装箱要装上一艘载重为 c 的轮船，其中集装箱 i 的分量为 wi，要求在装货体积不受限制的条件下尽力多装集装箱的解。
【思路】
先排序，而后抉择从最轻的开始装货物。
【代码实现】
这里就不提供具体代码了，因为感觉没有什么意义，最重要的是要先确定问题满足贪婪抉择性质，这样在很多时候，能够更容易的解决问题，这点很重要。
回溯法
说的直白点就是深度优先形式零碎搜寻问题的算法。
算法应用例子
【题目】
有一批共 n 个集装箱要装上两艘载重方别为 c1 和 c2 的轮船上，其中集装箱 i 的分量为 wi，且全副集装箱分量不大于两艘载重之和，问是否有一个装载计划实现装载。
【思路】
对第一艘船，结构一个 0 / 1 树，0 代表不抉择，1 代表抉择，而后别离去从根节点试图爬到叶节点，去一一记录下来可行的，抉择最小的为解，余下的判断第二艘船是否装的下即可。
【代码实现】
var weight1 = 30; // 第一艘船载重
var weight2 = 10; // 第二艘船载重
var w = [1, 9, 9, 4, 4, 9]; // 集装箱
var nowW1 = 0; // 以后载重
var nowBest1 = 0; // 以后最优装载
var n = w.length; // 集装箱个数
function Loading(deep) {if (deep > n) { // 如果达到根
if (nowW1 > nowBest1)
nowBest1 = nowW1;
return;
}
if (nowW1 + w[deep - 1] <= weight1) { // 如果 1 分支能够
nowW1 += w[deep - 1];
Loading(deep + 1);
nowW1 -= w[deep - 1];
}
// 0 分支
Loading(deep + 1);
}
function main() {Loading(1);
var firstLoad = nowBest1;
var all = 0;
for (var i = 0; i < n; i++) {all += w[i];
}
console.log("第一艘载重：" + firstLoad + "n");
if (all > weight2 + firstLoad) {console.log("失败 n");
} else {console.log("胜利 n");
}
}
main();分支限界
比照回溯法就很容易思考，用广度优先的方法，不断扩大以后节点的孩子为以后节点，次要是求解一个最优解，算法相比回溯法要简略些。
【题目】
有一批共 n 个集装箱要装上两艘载重方别为 c1 和 c2 的轮船上，其中集装箱 i 的分量为 wi，且全副集装箱分量不大于两艘载重之和，问是否有一个装载计划实现装载。
【思路】
借助队列，一层层来查看，找到最优解。
【代码实现】
var weight1 = 30; // 第一艘船载重
var weight2 = 10; // 第二艘船载重
var w = [1, 9, 9, 4, 4, 9]; // 集装箱
var nowBest1 = 0; // 以后最优装载
var n = w.length; // 集装箱个数
var arrayFIFO = [];
arrayFIFO.push([1, 1]); //deep, 此时曾经载重
arrayFIFO.push([1, 0]);
var nowBest1 = 1;
while (arrayFIFO.length > 0) {var nowNode= arrayFIFO.shift();
currentDeep = nowNode[0];
currentWeight = nowNode[1];
if (currentDeep >= n) {if (currentWeight > nowBest1) {nowBest1 = currentWeight;}
} else {arrayFIFO.push([currentDeep + 1, currentWeight]);
if (currentWeight + w[currentDeep] < weight1) {arrayFIFO.push([currentDeep + 1, currentWeight + w[currentDeep]]);
}
}
}
allW = 0;
for (val = 0; val < w.length; val++) {allW += w[val];
}
console.log("第一艘船载重：" + nowBest1);
if (allW <= nowBest1 + weight2) {console.log("胜利");
} else {console.log("失败");
}
