algorithm - 从两组中选择具有相同权重的项目

Question

假设我有两组元素。每个项目都有一个重量。我想找到与 B 组项目组合具有相同权重(或接近等于某个公差)的 A 组项目的所有组合。例如商品A1+A2重量与B1相同，但A2重量也可以是B2+B3。我可以使用什么方法？

Answer 1

假设您有 2n 个项目，每个项目的重量为 1。将任何 n 项放入 A 并将剩余项放入 B 的每个解决方案都会产生最佳负载差异 0；然而，有 2^n 个这样的解决方案。

这意味着一般来说，最优解的数量会随着项目的数量呈指数增长。因此，除非进行一些其他限制，否则不可能找到解决此问题的算法(在“运行时多项式限制在项目数中”的意义上)。

这里的动态编程算法可能不太有用，因为它们隐含地旨在修剪搜索树。