algorithm - 用遗传算法解决0-1背包问题是不是更好？

Question

背包问题是一个组合优化问题，在该问题中，必须在不超过背包容量的情况下最大限度地利用背包中的元素。我们知道解决这个问题的方法有很多种，遗传算法，动态规划，贪心法。我想知道与动态规划相比，使用遗传算法的优缺点是什么？空间复杂度、时间复杂度和最优性？

Answer 1

因此，为了回答这个问题，请务必考虑您认为最重要的因素:速度 或准确性

遗传算法 do not guarantee finding the most optimal solution但是，它们通常运行得非常快。

一些对遗传算法的快速描述可能会产生:

• 这是一个估计函数，不能保证找到全局最优解
• 它通常运行得非常快(在内存使用和复杂性方面)
• 实际计算很困难，因为遗传算法通常是特定问题且本质上是困惑的。它的复杂性可能看起来像一个很好的基础:O( O(适应度) * (O(突变) + O(交叉)))
  

但是，动态规划确实保证找到最佳解决方案，并获得更长的运行时间。动态规划的一些快速描述可能会产生:

• 它是一个精确函数 -- 保证收敛于最全局最优解
• 高内存使用率和很长的运行时间
• knapsack 01 问题的复杂度类似于:O(numItems * knapsackCapacity)，内存复杂度类似于O(knapsackCapacity)(为此归功于this post)

如果您要问什么是首选，那是特定主题。如果您想快速获得足够好的猜测，GA 可能是您的最佳选择。但是，如果您需要一个有保证和可验证的解决方案，DP 就是您的不二之选。

这应该满足基本的比较。