算法复杂度优于O(n^3)？

Question

我已经包括了我的方法和解决方案。我的解决方案工作得很好，但是，O(n^3)复杂度没有优化。

一个非政府组织正在运行种子分发程序。品种数量有限，品质多样。为了获得种子，农民需要要求种子的数量。种子分配只在周日进行，目标是最大限度地让农民获得相同类型的优质种子。

考虑到，非政府组织有以下种子和数量(按质量排序-最高)：

|Quality|Fruit1|Fruit2|Fruit3|
|-------|------|------|------|
|Highest|     3|     3|     1|
|Medium |     2|     0|     0|
|Low    |     4|     0|     0|

必需种子：

• 农民1: 2
• 农民2: 3
• 农民3: 1
• 农民4: 2
• 农民5: 3

产量:目标是将最高质量的种子分配给最大的农民。

• 农民1:最高Fruit1
• 农民2:最高- Fruit2
• 农民3:最高- Fruit1
• 农民4:中等- Fruit1
• 农民5:低Fruit1

在这里，农场主1号和3号组合要求获得3个种子，因此，组合中fruit1最高。

My approach (伪码)

我有以下的域类-农民，QualityType，FruitType，种子

QualityType有FruitType列表，其中有种子列表。

为了取得结果，我正在做以下工作：

• 从最高质量类型迭代到最低质量类型。
• 巢式迭代到果型和种子。
• 对于任何种子，请检查是否有farmer1要求相同数量的种子--要么单独使用，要么与任何其他种子组合。
• 如果不搬到农民二楼。
• 然而，这并不是优化的，因为它有3个嵌套循环。

你能建议一些算法来简化它吗？

Answer 1

最好的方法是首先划分问题空间，所以你只需要考虑多少农民想要多少特定水果类型和质量的种子。您可以在一次迭代中做到这一点。你需要知道每种水果和种子类型中有多少是被要求的。

然后，将每种品质的种子数除以所需的数量，舍入，并将剩余的种子分配给有限数量的农民。您可以通过将剩余部分确定为一个分数，并将多余的种子分配给该部分农民(例如7个种子，4个农民=1 1/3种子，这意味着农民获得的种子比他们要求的少1，如果农民计数器<= 7% 4，则额外获得1种子)(虽然如果分数小于1(4种子)，请求的种子数小于7，则会出现故障，在这种情况下，每个农民最初获得0颗种子，其余的种子仍然分配给以前的情况)。

这就产生了两个迭代:1构建一组农民的需求，另一次满足它们。