如何将长度拆分为子长度的组合（带有特殊允许的子长度的列表）

Question

背景是，我需要将绘制的长度拆分为有效的子部件，并在绘制时还需要捕捉到下一可能的长度。

例如我知道有效部分长度为[400，700，1200至1500年在十分之]

将导致3个规则：

• 规则1：值可以是400
• 规则2：值可以是700
• 规则3：值可以1200,1210，1220，... 1490，1500

实施例1

我绘制的1500的长度，我可以在2种方法拆分此：

• 方式1：2×400 + 1×700
• 方式2：1×1500

例2

我画了1150的长度，我不能将它分成有效的子部分

=>没有可能的解决方案......最近可能长度：1100或1200，让我们说，我们喜欢较小的一个

1100只能以一种方式分裂

• 1X 700 + 1X 400

所以我一直想找到

• 1）的下一个最佳长度和
• 2）的所有可能组合

创建此长度。

我将如何解决这个问题来解决它？最后，我想找出将子部件组合起来以获得总长度的可能方法。

目标：

我的最终目标是找到下一个最好的长度，并用最少的（最长）子部分组合，可以组合到这个长度...

Answer 1

天真的解决方案：递归。要么你适用规则1，要么你不适用。因此，对于输入1700，要么应用规则1（其余：1300）或者你不（剩下的：1700，不能再使用规则1）

Answer 2

从我所了解的情况来看，这个问题与更改问题。你的“有效部分”是硬币，你的长度是要给出的总变化。有几种方法可以解决这个问题，其中有动态编程和贪婪方法（根据问题的具体情况，其中一种可能比另一种更好）。 变更问题基本上是“如何获得所需的总和尽可能少的硬币，给予可能的硬币“。它在很多在线文档中都有描述。