使用遗传算法解决0-1背包问题会更好吗？

Question

背包问题是一个组合优化问题，其中必须最大化背包中物体的好处而不超过其容量。我们知道有很多方法可以解决这个问题，遗传算法，动态编程和贪婪方法。我想知道使用遗传算法与动态编程相比有什么优势和劣势？空间复杂性，时间复杂性和最优性？

Answer 1

因此，为了回答这个问题，重要的是要考虑您认为最重要的内容：速度或准确性

然而，遗传算法do not guarantee finding the most optimal solution通常运行得非常快。

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

• 它是一种估计函数，不保证找到全局最优解
• 它通常运行得非常快（内存使用和复杂性）
• 实际计算很难，因为遗传算法通常具有问题特异性和混乱性。它的复杂性可能是一个很好的基础：O( O(Fitness) * (O(mutation) + O(crossover)))

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

• 这是一个确切的功能 - 保证在最全局最优解决方案上的融合
• 内存使用率高，运行时间长
• 背包01问题的复杂性类似于：O(numItems * knapsackCapacity)，以及像O(knapsackCapacity)这样的记忆复杂性（this post的信用额度）

如果您问的是什么是首选，那是具体的主题。如果你想快速猜测，GA可能就是你要走的路。但如果您需要一个有保证且可验证的解决方案，那么DP就是您的选择。

这应该满足基本比较。