动态规划

参考
关键点：找到状态和状态转移方程；把大问题拆分成小问题再回归比较

示例

  1. 现在有硬币[1, 2, 3, 7, 10]的硬币，问凑足n元最少需要多少硬币？

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    function minimum(total, moneys) {
      const cache = {};
      const getMinimum = (totals) => {
        const list = moneys.map(i => {
          if (totals > i) {
            const nextIndex = totals - i;
            if (!cache[nextIndex]) {
              cache[nextIndex] = getMinimum(nextIndex);
            }
            if (cache[nextIndex]) {
              return [i].concat(cache[nextIndex])
            } else {
              return false
            }
          } else if (totals == i) {
            return [i]
          } else {
            return false
          }
        }).filter(i => !!i)
        if (list.length > 0) {
          return list.sort(function(a,b){return a.length-b.length})[0];
        } else {
          return []
        }
      }
      const back = getMinimum(total);
      return back;
    }
    minimum(13, [1, 2, 3, 7, 10])

  2. 背包问题
    有n 个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？

i 1 2 3 4
w(体积) 2 3 4 5
v(价值) 3 4 5 6 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function test(total, arr) {
  const unshift = arr.pop();
  console.log(arr, _.cloneDeep(arr));
  let next = [];
  if (arr.length > 0) {
    const bin1 = [unshift].concat(test(total - unshift[0], _.cloneDeep(arr)));
    const bin2 = test(total, _.cloneDeep(arr));
    const bin1W = bin1.map(item => item[0]).concat([0]).reduce(function(prev, curr){return prev + curr});
    const bin2W = bin2.map(item => item[0]).concat([0]).reduce(function(prev, curr){return prev + curr});
    if (bin1W > total && bin2W > total) {
      return []
    } else if (bin1W > total && bin2W <= total) {
      return bin2
    } else if (bin1W <= total && bin2W > total) {
      return bin1
    } else{
      const bin1V = bin1.map(item => item[1]).concat([0]).reduce(function(prev, curr){return prev + curr});
      const bin2V = bin2.map(item => item[1]).concat([0]).reduce(function(prev, curr){return prev + curr});
      return bin1V > bin2V ? bin1 : bin2
    }
  } else {
    if (unshift[0] > total) {
      return []
    } else {
      return [unshift]
    }
  }
}
const res = test(10, [[2, 3], [3, 4], [4, 5], [5, 6]]);
if (res.length <= 0) {
  console.log('无结果');
} else {
  console.log(`可以装：${JSON.stringify(res)}，价值是：${res.map(item => item[1]).reduce(function(prev, curr){return prev + curr})}`)
}

  1. 平面上有N*M个格子，每个格子中放着一定数量的苹果。你从左上角的格子开始， 每一步只能向下走或是向右走，每次走到一个格子上就把格子里的苹果收集起来， 这样下去，你最多能收集到多少个苹果。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    function test(arr) {
      const cache = {};
      const max = function(i, j) {
        console.log(i, j);
        if (i == arr.length - 1 && j == arr[0].length -1 ) {
          return [[i, j, arr[i][j]]]
        } else if (i == arr.length -1 ) {
          return [[i, j, arr[i][j]]].concat(max(i, j + 1));
        } else if (j == arr[0].length -1 ) {
          return [[i, j, arr[i][j]]].concat(max(i + 1, j));
        }
        const key = `${i}-${j}`;
        if (!cache[key]) {
          const rightList = max(i, j + 1);
          const leftList = max(i + 1, j);
          const rightListValue = rightList.map(item => item[2]).reduce(function(prev, curr){
            return prev + curr;
          });
          const leftListValue = leftList.map(item => item[2]).reduce(function(prev, curr){
            return prev + curr;
          });;
          cache[key] = [[i, j, arr[i][j]]].concat(rightListValue > leftListValue ? rightList: leftList);
        }
        return cache[key]
      }
      const list = [[0, 0, arr[0][0]]].concat(max(0, 0));
      console.log(cache, list, list.map(item => item[2]).reduce(function(prev, curr){
            return prev + curr;
          }))
    }
    test([
      [56, 85, 16, 1, 55, 79],
      [11, 87, 86, 94, 84, 54],
      [15, 94, 17, 11, 13, 97],
      [76, 60, 94, 21, 78, 49],
      [3, 16, 90, 86, 73, 45],
    ]);

  2. 无向图G有N个结点，它的边上带有正的权重值。
    你从结点1开始走，并且一开始的时候你身上带有M元钱。如果你经过结点i， 那么你就要花掉S[i]元(可以把这想象为收过路费)。如果你没有足够的钱， 就不能从那个结点经过。在这样的限制条件下，找到从结点1到结点N的最短路径。 或者输出该路径不存在。如果存在多条最短路径，那么输出花钱数量最少的那条。 限制：1<N<=100 ; 0<=M<=100 ; 对于每个i，0<=S[i]<=100。

遗传算法

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
具体而言，它有两个核心要点：第一是编码，即需要找到一种合适的方法，将待解决的问题映射为“基因”编码，生成多个个体；第二是评估，即需要一种定量的方法给每个个体打分，评估哪个个体所对应的方案更接近最佳答案，从而可以根据这个分数优胜劣汰。

示例

蚁群算法

介绍可以看下百度百科，里面还是讲的比较清楚。

思想

将蚁群算法应用于解决优化问题的基本思路为：用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解

实现

蚂蚁找到最短路径要归功于信息素和环境，假设有两条路可从蚁窝通向食物，开始时两条路上的蚂蚁数量差不多：当蚂蚁到达终点之后会立即返回，距离短的路上的蚂蚁往返一次时间短，重复频率快，在单位时间里往返蚂蚁的数目就多，留下的信息素也多，会吸引更多蚂蚁过来，会留下更多信息素。而距离长的路正相反，因此越来越多的蚂蚁聚集到最短路径上来。

示例

可应用的问题：旅行商问题、指派问题、Job—shop调度问题、车辆路由问题、图着色问题和网络路由问题等
本例实现“车辆路由问题”：

1
2