🗒️动态规划解决0/1背包问题

type
status
date
slug
summary
tags
category
icon
password
URL
 

0/1背包问题

0/1背包问题是一个经典的计算机科学问题，它描述了这样一个场景：一个背包有容量限制，我们需要从一堆物品中选择一些放入背包，使得背包的总价值最大化，且每个物品只能选择放入或不放入，不能放入部分。
 
优点：
  • 招式精妙，后发制人：动态规划就像一位老谋深算的武林高手，它不会蛮力破解难题，而是将难题拆解成一个个小招式，然后利用记忆，将已经破解的小招式的结果存入秘籍，遇到类似的招式时，直接从秘籍中调取结果，轻松化解。
  • 速度迅捷，出奇制胜：因为已经记忆了大量小招式的破解方法，所以动态规划在面对复杂难题时，能够以迅雷不及掩耳之势破解，让你在比拼速度的编程世界中立于不败之地。
缺点：
  • 占地为王，需谨慎：动态规划虽然招式精妙，但它需要占用大量的内存空间来存储秘籍，如果秘籍过大，可能会导致你的电脑不堪重负，甚至卡机死机。
  • 套路繁琐，易学难精：动态规划的招式看似简单，但想要真正掌握，却需要花费大量的时间和精力去练习，否则很容易在实战中出错，导致功亏一篑。
动态规划是一套威力强大的武林秘籍，但它也像一把双刃剑，使用得当，则能助你成就不世霸业；使用不当，则可能让你陷入困境。所以，学习动态规划，需要谨慎使用，并结合自身情况，选择合适的招式，才能在编程世界中笑傲江湖！
记住：
  • 动态规划适用于解决具有重叠子问题和最优子结构特性的问题。
  • 使用动态规划时，需要仔细分析问题，确定状态和状态转移方程。
  • 动态规划可能会占用大量的内存空间，需要谨慎使用。

动态规划

动态规划是一种解决这类具有重叠子问题和最优子结构特性的问题的算法。它通过将大问题分解为小问题，并存储小问题的解（通常在一个表格中），避免了重复计算，从而提高了效率。

计算步骤:

  1. 定义状态:
      2. 状态定义了子问题的解所需要的信息。对于0/1背包问题，我们可以定义状态 dp[i][j] 表示容量为 j 的背包在前 i 个物品中选择物品的最大价值。
  1. 状态转移方程:
      2. 状态转移方程描述了如何从子问题的解得到父问题的解。对于0/1背包问题，我们可以推导出以下状态转移方程：
      dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
      其中：
      • dp[i][j] 表示容量为 j 的背包在前 i 个物品中选择物品的最大价值。
      • dp[i - 1][j] 表示容量为 j 的背包在前 i - 1 个物品中选择物品的最大价值。
      • dp[i - 1][j - w[i]] 表示容量为 j - w[i] 的背包在前 i - 1 个物品中选择物品的最大价值。
      • w[i] 表示第 i 个物品的重量。
      • v[i] 表示第 i 个物品的价值。
  1. 初始化:
      2. 初始化是动态规划算法的开始步骤。对于0/1背包问题，我们可以将 dp[0][j] 初始化为 0，表示容量为 j 的背包不选择任何物品的最大价值为 0。
  1. 求解:
      2. 根据状态转移方程，我们可以从下往上、从左往右依次计算 dp[i][j] 的值，直到计算出 dp[n][m] 的值，即为背包装载物品的最大价值，其中 n 是物品的总数，m 是背包的容量。
  1. 回溯:
      2. 求出 dp[n][m] 的值后，我们可以通过回溯找到最优解。从 dp[n][m] 开始，一直回溯到 dp[0][0]，记录回溯过程中找到的物品，即可得到最优解对应的是哪些物品。
 

代码示例

javascript

function knapsack(items, capacity) {
  const n = items.length;
  const m = capacity;
  const dp = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));

  // 初始化
  for (let i = 0; i <= n; i++) {
    dp[i][0] = 0;
  }

  // 状态转移
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      dp[i][j] = dp[i - 1][j];
      if (j >= items[i - 1].weight) {
        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - items[i - 1].weight] + items[i - 1].value);
      }
    }
  }

  // 回溯
  let i = n;
  let j = m;
  const selectedItems = [];
  while (i > 0 && j > 0) {
    if (dp[i][j] !== dp[i - 1][j]) {
      selectedItems.push(items[i - 1]);
      i--;
      j -= items[i - 1].weight;
    } else {
      i--;
    }
  }

  return {
    value: dp[n][m],
    selectedItems,
  };
}

const items = [
	{ weight: 5, value: 12 },
  { weight: 1, value: 10 },
  { weight: 2, value: 5 },
  { weight: 3, value: 15 },
 ]
 
 knapsack(items, 8)
JavaScript

© black-black-cat 2021-2025