动态规划

很多[最优解]的问题都可以考虑使用动态规划解决

动态规划包括两个核心思想

  1. 状态转移方程

是指把一个大问题分解为多个重叠的子问题,寻找重叠子问题之间的关系
比如菲薄拉起数列的状态转移方案

如果4. 动态规划算法 - 图1表示斐波拉契数列的第n位的值
则有4. 动态规划算法 - 图2

在使用动态规划时,最苦难的就是找到状态转移方程

  1. db 缓存表

在求解的过程中,可能会遇到对相同的参数多次求解,为避免重复计算,可以使用缓存表将解值缓存下来

0-1背包问题

有一个背包,容积为c

给定一个物品列表: [o1,o2,o3,o4,...],每个物品都有两个属性,分别是价值和体积,例如{v:10,p:5}

问: 应该如何选择装入背包的物品,使得背包中的物品的总价值最大?

基础版

  1. /***
  2.  * 
  3.  * 获取0-1背包问题的最优解
  4.  * @param {Number} c背包体积
  5.  * @param {{v:Number,p:Number}[]} list 物品列表
  6.  * @returns {Number} 返回最大值
  7.  * 
  8.  * 
  9.  */
  10. function package(c, list) {
  12.     /**
  13.      * @param {Number} i
  14.      * @param {Number} rest;
  15.      */
  16.     function _package(i, rest) {
  17.         // 如果不从当前的物品列表拿
  18.         if (i >= list.length) {
  19.             return 0;
  20.         }
  21.         const currPro = list[i];
  22.         if (currPro.v > rest) {
  23.             // 商品的体积大于剩余的空间了,商品一定不能拿,拿下一个
  24.             return _package(i + 1, rest)
  25.         } else {
  26.             // 当选择这件物品的时候
  27.             const selected = currPro.p + _package(i + 1, rest - currPro.v);
  28.             // 当不选这件物品的时候胡
  29.             const unSelected = _package(i + 1, rest);
  30.             return Math.max(selected, unSelected)
  31.         }
  32.     }
  33.     return _package(0, c)
  35. }
  37. const list = [
  38.     { v: 10, p: 5 },
  39.     { v: 7, p: 4 },
  40.     { v: 11, p: 8 },
  41.     { v: 9, p: 6 },
  42.     { v: 2, p: 1 },
  43.     { v: 17, p: 20 },
  44.     { v: 25, p: 30 },
  45. ]
  46. const c = 40;
  47. const result = package(c, list);
  48. console.log('result', result)

升级版

  2. /**
  3.  * 
  4.  * @param {Number} c  背包的体积
  5.  * @param {Array} rest  剩余商品
  6.  * @returns  {{value:Number,choose:Number []}} max 最大值
  7.  */
  8. function package(c, rest) {
  9.     /**
  10.      * 
  11.      * @param {Number} n  开始拿的位置
  12.      * @param {Number} rest  剩余空间
  13.      */
  14.     function _package(n, rest) {
  15.         // 超出可以挑选商品的范围
  16.         if (n >= list.length) {
  17.             return {
  18.                 value: 0,
  19.                 choose: []
  20.             }
  21.         }
  22.         // 获取当前商品
  23.         const product = list[n];
  24.         // 当前商品的体积大于背包剩余的体积
  25.         if (product.v > rest) {
  26.             const next = _package(n + 1, rest);
  27.             return {
  28.                 value: next.value,
  29.                 choose: [0, ...next.choose]
  30.             }
  31.         } else {
  32.             // 选择当前物商品的价值
  33.             let next = _package(n + 1, rest - product.v);
  34.             let select = {
  35.                 value: product.p + next.value,
  36.                 choose: [1, ...next.choose]
  37.             }
  38.             // 不选择当前物品的机制
  39.             next = _package(n + 1, rest);
  40.             let unselect = {
  41.                 value: next.value,
  42.                 choose: [0, ...next.choose]
  43.             }
  44.             if (select.value > unselect.value) {
  45.                 return select;
  46.             } else {
  47.                 return unselect;
  48.             }
  50.         }
  51.     }
  53.     return _package(0, c)
  54. }
  58. const list = [
  59.     { v: 10, p: 5 },
  60.     { v: 7, p: 4 },
  61.     { v: 11, p: 8 },
  62.     { v: 9, p: 6 },
  63.     { v: 2, p: 1 },
  64.     { v: 17, p: 20 },
  65.     { v: 25, p: 30 },
  66. ]
  67. const c = 40;
  68. const result = package(c, list);
  69. console.log('result', result)

至尊版

  2. /**
  3.  * 
  4.  * @param {Number} c  背包的体积
  5.  * @param {Array} rest  剩余商品
  6.  * @returns  {{value:Number,choose:Number []}} max 最大值
  7.  */
  8. function package(c, rest) {
  9.     // 缓存
  10.     const dp = {}
  11.     /**
  12.      * 
  13.      * @param {Number} n  开始拿的位置
  14.      * @param {Number} rest  剩余空间
  15.      */
  16.     function _package(n, rest) {
  17.         // 超出可以挑选商品的范围
  18.         if (n >= list.length) {
  19.             return {
  20.                 value: 0,
  21.                 choose: []
  22.             }
  23.         }
  24.         const key = `${n}-${rest}`;
  25.         if (dp[key]) {
  26.             return dp[key];
  27.         }
  28.         // 获取当前商品
  29.         const product = list[n];
  30.         // 当前商品的体积大于背包剩余的体积
  31.         if (product.v > rest) {
  32.             const next = _package(n + 1, rest);
  33.             dp[key] = {
  34.                 value: next.value,
  35.                 choose: [0, ...next.choose]
  36.             }
  37.         } else {
  38.             // 选择当前物商品的价值
  39.             let next = _package(n + 1, rest - product.v);
  40.             let select = {
  41.                 value: product.p + next.value,
  42.                 choose: [1, ...next.choose]
  43.             }
  44.             // 不选择当前物品的机制
  45.             next = _package(n + 1, rest);
  46.             let unselect = {
  47.                 value: next.value,
  48.                 choose: [0, ...next.choose]
  49.             }
  50.             if (select.value > unselect.value) {
  52.                 dp[key] = select;
  53.             } else {
  54.                 dp[key] = unselect;
  55.             }
  56.         }
  57.         return dp[key];
  59.     }
  60.     const result = _package(0, c);
  61.     console.log('dp', dp)
  62.     return result;
  63. }
  67. const list = [
  68.     { v: 10, p: 5 },
  69.     { v: 7, p: 4 },
  70.     { v: 11, p: 8 },
  71.     { v: 9, p: 6 },
  72.     { v: 2, p: 1 },
  73.     { v: 17, p: 20 },
  74.     { v: 25, p: 30 },
  75. ]
  76. const c = 40;
  77. const result = package(c, list);
  78. console.log('result', result)