动态规划

动态规划算法

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

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

 

求解思路

动态规划算法可分解成从先到后的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]}

 

背包问题数据表

物品号i 1 2 3 4 5 6
体积C 2 3 1 4 6 5
价值W 5 6 5 1 19 7

前i件物品选若干件放入空间为j的背包中得到的最大价值表

0 1 2 3 4 5 6 7 8 9 10
0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 5 5 5 5 5 5 5 5 5
2 0 5 6 6 11 11 11 11 11 11 11
3 0 5 5 10 11 11 16 16 16 16 16
4 0 5 5 10 11 11 16 16 16 16 17
5 0 5 5 10 11 11 19 24 24 29 30
6 0 5 5 10 11 11 19 24 24 29 30

 

实现代码:

/* 动态规划算法 */

//比较
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);

本文链接地址: 动态规划

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注