背包最大价值问题

78 阅读 0 评论 52 点赞

我是靠谱客的博主虚幻大雁，最近开发中收集的这篇文章主要介绍背包最大价值问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

背包最大价值问题

有容量为 4 的背包，有三个物品，属性用两个数组分别表示每个物品的体积和价值
$3]\ val = [4, 2, 3]$
求背包能装下的最大价值

定义二维数组
在这里插入图片描述

let vol = [2, 1, 3];
let val = [4, 2, 3];

function dp(S, i) {
  if (i === 0) {
    if (S >= 2) {   // 能装下第一个物品
      return 4;
    } else {       // 装不下第一个物品
      return 0;
    }
  }
  if (S < vol[i]) {
    return dp(S, i - 1);
  }
  return Math.max(val[i] + dp(S - vol[i], i - 1), dp(S, i - 1));
}

function knapsack(N, W, vol, val) {
  // 初始化全 0 二维数组
  let dp = [];
  let arr = new Array(W + 1).fill(0);
  for (let i = 0; i < N + 1; i++) {
    dp.push(Array.from(arr)); //要加 Array.from 否则后面 假设改dp[1][3] 那所有 dp[x][3] 都会变
  }

  for (let i = 1; i <= N; i++) {
    for (let w = 1; w <= W; w++) {
      if (w - vol[i - 1] < 0) {
        dp[i][w] = dp[i - 1][w];
      } else {
        dp[i][w] = Math.max(
          dp[i - 1][w],    // 不选
          dp[i - 1][w - vol[i - 1]] + val[i - 1]   // 选
        );
      }
    }
  
  return dp;
}
knapsack(3, 4, vol, val);