动态规划算法

动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

求解思路

动态规划算法可分解成从先到后的4个步骤：

• 描述一个最优解的结构；
• 递归地定义最优解的值；
• 以“自底向上”的方式计算最优解的值；
• 从已计算的信息中构建出最优解的路径。

背包问题

有N件物品和一个容量为V的背包。（每种物品均只有一件）第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大?

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

背包问题数据表

实现代码:

/* 动态规划算法 */

//比较
function max(a, b) {
  return (a > b) ? a : b;
}

//数组中去除重复的算法
Array.prototype.uniq = function() {
  this.sort();
  let re = [this[0]];
  for (let i = 1; i < this.length; i++) {
    if (this[i] !== re[re.length - 1]) {
      re.push(this[i]);
    }
  }
  return re;
}

function dynamicPack(capacity, size, value) {
  let arr = new Array();
  let n = size.length; //item 的数量
  let k = new Array();
  let res = '';
  //手动构建二维array
  for (let i = 0; i <= capacity + 1; i++) {
    k[i] = [];
  }
  for (let i = 0; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      if (i == 0 || w == 0) {
        k[i][w] = 0; //表示当物体为前面i个,背包容量为w的最大价值
      } else if (size[i - 1] <= w) { //大小为size[i-1]的物品可以放入背包时
        k[i][w] = max(value[i - 1] + k[i - 1][w - size[i - 1]], k[i - 1][w]);
        if (k[i][w] != k[i - 1][w])
          arr.push(value[i - 1]);
      } else { //大小为size[i-1]的物品不能放入背包时
        k[i][w] = k[i - 1][w];
      }
      res += k[i][w];
      res += '---';
    }
    res += '\n';
  }

  console.log(res);

  let unarr = arr.uniq();
  let tem = 0;
  let re = [];
  //k[n][capacity]是总价
  for (let i in unarr) {
    if (tem <= k[n][capacity]) {
      re.push(unarr[i]);
      tem += parseInt(unarr[i]);
    }
  }
  return k[n][capacity]; //最大价值
}

/* 算法调用 */
let value = [5, 6, 5, 1, 19, 7]; //价值
let size = [2, 3, 1, 4, 6, 5]; //尺寸
let capacity = 10; //背包容量
let result = dynamicPack(capacity, size, value);
console.log(result);