比方说，我有问题是这样的：
- 背包容量= 20000000
- 项目数= 500
- 每个项目的重量是100之间的随机数20万
- 每个项目的利润是介于1至10的随机数
因此，这是我的问题的最好方法是什么？ GA或者动态规划？
请给我一个简单的解释，正如我在我新手..
Answer 1:
动态规划（DP）：
- 精确算法 - 查找全局最优解
- 运行时间长
- 使用了大量的内存
- 很简单实现
遗传算法（GA）：
- 估计 - 并不一定找到全局最优解
- 短期运行时间
- 内存使用取决于个体的数量，但一般是可管理
- 溶液的质量取决于选择一个有效的表示+让它运行足够长的时间
- 相当简单的实现，设计决策可能会稍微复杂一些，特别是如果你没有气体显著经验
爬山：
- 估计 - 并不一定找到全局最优解。 更应以一个停止局部最优比GA，虽然有很多方法可以减少这种情况发生的几率
- 短期运行时间
- 极低的内存使用情况
- 很简单实现
DP（或为NP完全问题的任何确切的算法），一般只适用于一个合理的小问题是一个好主意，或者如果找到全局最优是最重要的事情。
有2种方法DP：（有一个相当简单的优化，其中只存储2行，我的内存使用情况分析的推移，这种优化使用的假设）
已经项的矩阵X的重量，与细胞的值作为最大值
矩阵大小= 500×20 000 000
运行时间= O（500 * 20 000 000）= O（10 000 000 000）
存储器=最大10 * 500 - > 000 5 - >短= 2个字节 - > 2 * 20 000 000 * 2 = 80 000 000 <80 MB
说明：下面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×10 * 500
运行时间= O（500 * 10 * 500）= O（2 500 000）
存储器=最大值20 000 000 - > INT = 4字节 - > 2 * 500 * 4 = 000 4 <4 KB
说明：下面A [I，J]表示从元件1的任意子集可获得的最低重量为i与值等于 j。 下面的更新规则意味着 - 既找不到不包括当前元素（因此重量和价值保持不变），或包括它（以便查找为（当前值减去当前项的值的最佳值之间的最佳值），并添加重当前项目的话）。 在任何单元中的值是一个子集以产生该值的准确的重量，所以我们需要通过所有小区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仍接近忽略不计）（注这是远离规则，任何情况下，需要在自己的权利进行分析）。
Answer 2:
动态规划在时间运行O(numItems * knapsackCapacity)和O(knapsackCapacity)内存。 这意味着，对于您的要求，你会：
- 约
20.000.000 x 500 = 10.000.000.000行动-可能会在完成了几个小时，这取决于你的机器上执行; - 因为一个项目的利润最多为10，你最多只能有500个项目，这意味着你的最大理论利润不能超过
10 x 500 = 5000。 这可以在2个字节（短）来表示。 所以，你还需要2 x 20.000.000 / 1024 / 1024 ~= 38 MB的内存来存储您的DP阵列。 再次，不算多。
其他人已经提到各自的优势和缺点。 GA将更快地完成，但DP解决方案还应该完成在几个小时内，它会给你一个确切的答案。
就个人而言，我会选择DP如果等待了几个小时的解决方案是没有问题的。
注意：这里是与运行DP O(knapsackCapacity)内存：
dp[i] = maximum profit obtainable for weight i
for i = 1 to numItems do
for j = knapsackCapacity down to items[i].weight do
dp[j] = max(dp[j], dp[j - items[i].weight] + items[i].profit)
Answer 3:
有没有“最好”的方法，每一个都有它的优点和缺点。
在这种情况下，权衡是找到解决方案的最优性之间 - GA不以任何方式保证找到最佳的解决方案。
而所需的时间/空间来计算的解决方案 - 使用动态规划能节省一些多余的计算，但你仍然要计算所有可能的组合至少一次，以找到最佳的解决方案（或者甚至任何人在所有的解决方案）。
Answer 4:
首先，你需要考虑动态规划为一个确切的算法，该算法可以保证的答案将是最佳的答案。 在另一方面GA是一种启发式算法通常收敛到局部最优。 存在用于背包动态编程溶液其是伪线性（O（容量* NUMBER_OF_ITEMS）），如果他们是整数。 在你的情况，你需要大约1E10操作和记忆。 这是一台计算机是可行的。 因此，如果找到最佳的答案是对你很重要，你有足够的时间（在几个小时的顺序），你可以使用动态规划方法。 否则，你可能更愿意使用启发式算法，如GA。
文章来源: Which is the best method between Genetic Algorithm and Dynamic Programming to solve classic 0-1 knapsack? [closed]
