这是NP完全的吗？
Is this NP-Complete?
所以我有 N 个苹果位于二维坐标平面的点上，还有一个点 P。
我还有 X 辆手推车，每辆都有最大容量 Y。我想把所有的苹果都拿去点 P 。
我需要找到一种安排（每辆手推车要采摘哪些苹果），以尽量减少每辆手推车必须行驶的总距离。
- 没有起点，您可以在
N 个点中的任何一个点开始购物车。
- 每辆手推车可以装任意数量的苹果 <=
Y.
这个问题有没有比暴力破解更好的解决方案，O(N^Y)
所描述的问题 NP 是完整的，因为它是 Euklidean Travelling Salesman Problem; it contains the special case where there is X=1 cart with capacity N. The problem stated in the question is termed a Vehicle Routing Problem 的概括，因为涉及多个购物车。
所以我有 N 个苹果位于二维坐标平面的点上，还有一个点 P。
我还有 X 辆手推车，每辆都有最大容量 Y。我想把所有的苹果都拿去点 P 。
我需要找到一种安排（每辆手推车要采摘哪些苹果），以尽量减少每辆手推车必须行驶的总距离。
- 没有起点，您可以在
N个点中的任何一个点开始购物车。 - 每辆手推车可以装任意数量的苹果 <=
Y.
这个问题有没有比暴力破解更好的解决方案，O(N^Y)
所描述的问题 NP 是完整的，因为它是 Euklidean Travelling Salesman Problem; it contains the special case where there is X=1 cart with capacity N. The problem stated in the question is termed a Vehicle Routing Problem 的概括，因为涉及多个购物车。