我有 3 个盒子 - B1、B2、B3。每个盒子最初包含 3 种不同水果的混合物 - 苹果、橙子、芒果。我们的目标是以每个盒子只包含一种水果的方式排列盒子中的水果。因此,您需要将水果从一个盒子转移到另一个盒子以便进行排列。如何用最少的 Action 做到这一点?
假设给出了 9 个整数。由于每个盒子最初包含所有 3 种水果,您可以将 9 个整数分成 3 组,每组分别代表 B1、B2、B3 中水果的初始排列。考虑:10、17、20、32、29、19、43、27、28。水果按苹果、橙子和芒果的顺序表示。所以第一个盒子里有 10 个苹果、17 个橙子和 20 个芒果等等。
要使上述盒子只包含一种水果,最少需要移动多少次。任何盒子都可以包含任何一种水果。
最佳答案
解决此问题的一种方法是将其表示为分配问题,然后使用 Hungarian algorithm找到最优解。这将具有 O(n^3) 的复杂度,其中 n 是框的数量。
要将其表达为一项任务,请将问题视为尝试为每个框分配一个标签以显示其最终内容。该作业的分数由当前未包含在盒子中的水果的数量给出。
因此,例如,如果第一个盒子包含 10 个苹果、17 个橙子和 20 个芒果,总共有 85 个苹果,那么将苹果标签分配给第一个盒子的成本为 85-10 = 75。
关于algorithm - 将水果放入盒子中的最小 Action ,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31964063/