-1

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

例如，我知道有效的零件长度是 [400, 700, 1200 - 1500 in 10ths]

这将导致 3 条规则：

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

示例 1

我画了 1500 的长度，我可以用 2 种方式分割它：

  • 方式一：2x 400 + 1x 700
  • 方式2：1x 1500

示例 2

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

=> 没有可能的解决方案...最接近的可能长度：1100 或 1200，假设我们更喜欢较小的

1100只能以一种方式拆分

  • 1x 700 + 1x 400

所以我总是想找到

  • 1) 次佳长度和
  • 2) 所有可能的组合

创建这个长度。

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

目标：

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

4

2 回答 2

0

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

于 2013-07-16T12:56:20.803 回答
0

据我了解，这个问题与Change-making 问题密切相关。你的“有效部分”是硬币，你的长度是要给的总零钱。有几种方法可以解决这个问题，其中包括动态规划和贪心法（根据问题的具体情况，一种可能比另一种更好。）改变问题基本上是“如何使用给定可能的硬币，尽可能少的硬币”。它在许多在线文档中都有描述。

于 2013-07-16T13:39:15.513 回答