遗传算法和动态规划哪个是解决经典0-1背包问题的最佳方法？ [关闭]

假设我有这样的问题：

• 背包容量=2000万
• 商品数量 = 500
• 每件物品的重量是100到2000万之间的随机数
• 每个项目的利润是1到10之间的随机数

那么哪种方法是解决我的问题的最佳方法呢？遗传算法还是动态规划？

请给我一个简单的解释，因为我是这方面的新手..

动态规划（DP）：

• 精确算法 - 寻找全局最优解
• 运行时间长
• 占用大量内存
• 实施起来非常简单

遗传算法（GA）：

• 估计——不一定能找到全局最优解
• 运行时间短
• 内存使用量取决于个体数量，但通常是可以管理的
• 解决方案的质量取决于选择有效的表示+让它运行足够长的时间
• 实施起来相当简单，但设计决策可能会稍微复杂一些，特别是如果您没有丰富的 GA 经验的话

爬山：

• 估计 - 不一定能找到全局最优解。更多可能会停在局部最优 http://en.wikipedia.org/wiki/Local_optimum与 GA 相比，尽管有一些方法可以减少这种情况发生的可能性
• 运行时间短
• 内存使用率非常低
• 实施起来非常简单

DP（或 NP 完全问题的任何精确算法）通常仅对于相当小的问题或者寻找全局最优是最重要的事情时才是一个好主意。

有 2 种 DP 方法：（有一种相当简单的优化，您只存储 2 行，我的内存使用分析是基于使用这种优化的假设）

• 有一个由项目 x 重量组成的矩阵，单元格值为最大值

  矩阵大小 = 500 x 20 000 000

  运行时间 = O(500 * 20 000 000) = O(10 000 000 000)

  内存 = 最大 10 * 500 -> 5 000 -> 短 = 2 字节 -> 2 * 20 000 000 * 2 = 80 000 000

  解释：下面的 A[i,j] 表示从具有权重的元素 1 到 i 的任意子集中可获得的最佳（最高）值小于或等于j。下面的更新规则意味着 - 找到不包含当前元素（因此权重和值保持不变）或包含它之间的最佳值（因此查找（当前权重减去当前项目的权重）的最佳值并添加当前项目的值）。然后只需返回 A[500, 20000000]，它表示从具有背包大小最大重量的所有元素的任何子集中可获得的最高值。

  算法：

  A[0, 0..20000000] = 0
  for i = 1:500
  for x = 0:20000000
    A[i, x] = max(A[i-1, x], value(i) + A[i-1, x-weight(i)])
  // ignore value(i) + A[i-1, x-weight(i)] when weight(i) > x
  return A[500, 20000000]
  

• 有一个由项目 x 值组成的矩阵，单元格值为最小权重

  矩阵大小 = 500 x 10*500

  运行时间 = O(500 * 10*500) = O(2 500 000)

  内存 = 最大 20 000 000 -> int = 4 字节 -> 2 * 500 * 4 = 4 000

  解释：下面的 A[i,j] 表示从具有 value 的元素 1 到 i 的任意子集中可获得的最低权重equal toj。下面的更新规则意味着 - 找到不包含当前元素（因此权重和值保持不变）或包含它之间的最佳值（因此查找（当前值减去当前项目的值）的最佳值并添加当前项目的重量）。任意单元格的值为exact子集的权重来产生该值，因此我们需要查看所有单元格 A[500, x]，它表示任何值 x 的元素的最小权重子集。

  算法：

  A[0, 0] = 0
  A[0, 1..5000] = ∞
  for i = 1:500
  for x = 0:5000
    A[i, x] = min(A[i-1, x], weight(i) + A[i-1, x-value(i)])
  // interpret A[i-1, x-value(i)] as 0 when value(i) > x
  return largest x that A[500, x] <= 20000000
  

所以，是的，复杂性几乎是不言而喻的，第一种方式你将等待几个小时，但第二种方式只需几秒钟，并且内存使用量也有类似的差异（尽管 80 MB 仍然几乎可以忽略不计）（注意这是FAR根据规则，每个案例都需要单独分析）。