如何將長度拆分爲子長度的組合（帶有特殊允許的子長度的列表）

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

從我所瞭解的情況來看，這個問題與更改問題。你的「有效部分」是硬幣，你的長度是要給出的總變化。有幾種方法可以解決這個問題，其中有動態編程和貪婪方法（根據問題的具體情況，其中一種可能比另一種更好）。 變更問題基本上是「如何獲得所需的總和儘可能少的硬幣，給予可能的硬幣「。它在很多在線文檔中都有描述。