算法设计

分

治

合（关键）

• Break up problem of size n into two equal parts of size 1⁄2 n.
• Solve two parts recursively.
• Combine two solutions into overall solution in linear time.

Brute force: n2.

Divide-and-conquer: n log n.（以2为底）

双指针法

p(j) = largest index i < j such that job i is compatible with j.

这里 Find-Solution 是一个函数名字。

实现中也用到了递归。

const items = [
{ w: 1, v: 3 },
{ w: 2, v: 7 },
{ w: 3, v: 12 },
];
const W = 5; //背包的最大容量
console.log(knapsack(items, W));

function knapsack(items, W) {
let M = [],
len = items.length;

// 初始化二维数组
for (let i = 0; i < len; i++) {
M[i] = new Array(W + 1).fill(0);
}
// 初始化只考虑序号 <= 0 的物品
for (let i = 0; i < W + 1; i++) {
M[0][i] = items[0].w <= i ? items[0].v : 0;
}
console.table(M);
for (let i = 1; i < len; i++) {
for (let w = 0; w <= W; w++) {
let cW = items[i].w,
cV = items[i].v;
if (cW > w) {
M[i][w] = M[i - 1][w];
} else {
M[i][w] = Math.max(M[i - 1][w - cW] + cV, M[i - 1][w]);
}
}
}
console.table(M);
let maxV = M[len - 1][W];
// 如何得到最大价值的物品组合呢？？
let arr = M[len - 1];
let combinedItemIndex = getCombinedItemIndex(arr, items);
return { maxV, combinedItemIndex };
}

There is a stairs with a height of 10 steps. You can climb stairs only by two or three steps. So you can go by _____ different kinds of ways.

function steps(n) {
//第几个元素（元素下标+1）代表有多少个台阶，元素值代表此台阶级数（第几个元素）下有多少种走法
//将结果缓存在对象中会比数组好理解，以后用对象来存结果
let M = [0, 1, 1];
for (let i = 3; i < n; i++) {
M[i] = M[i - 2] + M[i - 3];
}
return M[n - 1];
}
console.log(steps(10));

Using dynamic programming to solve the following integer linear programming, the objective value is _____

integerLinear();
function integerLinear() {
let Max=10;//此题 x1 x2 x3 都为0时的结果

//循环的初始条件用到了动态规划
for (let x1 = 0; x1 <= 4; x1++) {
for (let x2 = 4 - x1; x2 >= 0; x2--) {
for (let x3 = 4 - x1 - x2; x3 >= 0; x3--) {
let value =
5 * x1 * x1 +
3 * x2 * x2 +
x3 * x3 -
10 * x1 -
3 * x2 +
2 * x3 +
10;
if(value>Max){
Max=value
}
}
}
}
console.log(Max)
return Max
}

下面的方式是我 2019.12.18 闭卷手写的，用了尾递归的方案
注意递归调用时不能改变原 result 与 source

// 全排列 2019.12.18 闭卷手写成功 开心^3^
// [1,2,3]=>
// [1,2,3] [1,3,2]
// [2,1,3] [2,3,1]
// [3,1,2] [3,2,1]
function allSequence(arr) {
// 思路是 result 参数是用来携带排列结果的数组
// 循环 source 中的项目，从 source 参数中选一项，push 到递归函数的 result 参数里，
// 同时递归函数的 source 参数要减少这一项
const arrangeOneFromSource = function(result, source) {
if (source.length === 0) {
// 递归出口 一个排列完成了
// 处理排列结果 这里就打印好了
console.log(result);
return result;
}

// 这下面算是动态规划的基本思路
for (let i = 0; i < source.length; i++) {
const ele = source[i];

// 注意递归调用时不能改变原 result 与 source 入参，
// 不然一次排列完成后，原 result 参数已经是第一种排列的结果，source 参数也成了空数组，
// source.length===0，这个循环体也不会再执行了
// 要生成新的数组当递归函数的入参
// 用 concat 与 slice 来生成新的数组
// 不要用 push 或 splice 来改变原数组

// 这个函数算尾递归
arrangeOneFromSource(
    result.concat([ele]),
    source.slice(0, i).concat(source.slice(i + 1))
);
}
};
// 初始调用
arrangeOneFromSource([], arr);
}
allSequence([1, 2]);

//  八皇后 12.20日闭卷手写
//  8*8棋盘的里面的位置描述：
// 2020/01/24
// 其实就用一个一维的数组就可以表示，下标表示行，下标对应的值表示这行的棋子放哪列

eightQueen();

function eightQueen() {
//这里的 count 一定要定义在调用 processLine 方法的前面
let count = 0;

processLine(0, []);

function processLine(n, result) {
if (n === 8) {
//出口，处理结果
console.log(result);
console.log(++count);
return result;
}

// 下面算是动态规划的基本思路
// 尝试每一列的位置
for (let j = 0; j < 8; j++) {
let curPos = j;
// 判断是否和之前的项目不冲突
if (!isConflict(result, curPos)) {
// 不冲突就进入下一行
// 递归调用函数时 result 参数合并上此位置
// 这里不能用 push 改原 result 参数数组，
// 不然在同一行遍历下一个位置的时候，result 参数已经被塞过上一轮的数值了
  processLine(n + 1, result.concat([curPos]));
}
}
}
function isConflict(arr, item) {
let arrL = arr.length;
for (let i = 0; i < arrL; i++) {
const ele = arr[i];
if (isConflictWithItem([i, ele], [arrL, item])) {
return true;
}
}
return false;
}

//[r1,c1],[r1,c1]
function isConflictWithItem([r1, c1], [r2, c2]) {
if (r1 === r2 || c1 === c2) return true;
let rowDis = r1 - r2,
colDis = c1 - c2;
if (rowDis === colDis || rowDis === -colDis) return true;
return false;
}
}

// 二维数组环形遍历
const arr = [
[1, 2, 3, 31],
[4, 5, 6, 61],
[7, 8, 9, 91],
[10, 11, 12, 13]
];
const arr1 = [
[1, 2, 3, 31],
[4, 5, 6, 61],
[7, 8, 9, 91]
];
const arr2 = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9],
[10, 11, 12]
];

circleTraverse(arr2);

最长递增子序列意思是在一组数字中，找出最长一串递增的数字，比如

0, 3, 4, 17, 2, 8, 6, 10

对于以上这串数字来说，最长递增子序列就是 0, 3, 4, 8, 10，可以通过以下表格更清晰的理解

通过以上表格可以很清晰的发现一个规律，
找出刚好比当前数字小的数，并且在小的数组成的长度基础上加一。

这个问题的动态思路解法很简单，直接上代码

function lis(n) {
if (n.length === 0) return 0
// 创建一个和参数相同大小的数组，并填充值为 1
let array = new Array(n.length).fill(1)
// 从索引 1 开始遍历，因为数组已经所有都填充为 1 了
for (let i = 1; i < n.length; i++) {
// 从索引 0 遍历到 i
// 判断索引 i 上的值是否大于之前的值
for (let j = 0; j < i; j++) {
  if (n[i] > n[j]) {
    array[i] = Math.max(array[i], 1 + array[j])
  }
}
}
let res = 1
for (let i = 0; i < array.length; i++) {
res = Math.max(res, array[i])
}
return res

参考

给出一个实际金额，比如40

以及一个优惠券面额列表比如[30, 50, 100],每种优惠券数量不限

要求返回能组合成实际金额的最大值，
比如：实际金额40 -> 返回30；
80 -> 80=30+50；
110 -> 110=30+30+50

测试

代码

可以用 queue 实现，在 while 循环中动态 push 与 shift，直到 queue 清空
其他实现方式待会查

美国邮政系统

唯一可能是最优的算法

区间安排问题中贪婪算法是最优解

是最优算法，证明其最优内容比较多，以后有需要再看

子主题

应用

Kruskal's algorithm（目前感觉这个算法思路与实现更简单）

Prim's algorithm

Divide objects into k non-empty groups. Find a k-clustering of maximum spacing

Single-link k-clustering algorithm

回溯算法求解八皇后问题的原则是：有冲突解决冲突，没有冲突往前走，无路可走往回退，走到最后是答案。

代码