算法--杆切割算法

Question

我们得到了m米的杆数，我们希望做以下操作：

• 切割n1长度的m1棒
• 切割n2长度的m2棒
• ……

解决这一问题的贪婪方法是什么？

我已经尝试了标准的回溯问题，但这是缓慢的。是否有一个贪婪的方法来解决这个问题？

同时，我也注意到n1xm1产品的最高共同因素是n2xm2.应该是n，虽然我对此不确定，但对我来说似乎是相当正确的。

示例：

n=20
m=40

n1=20 m1=12
n2=40 m2=10
n3=10 m3=6
n4=25 m4=4

(240,400，60,100)的HCF是20，这意味着这个问题是可以解决的，但是我不知道我贪婪的方法。

Answer 1

一种贪婪的方法是在每次迭代中切一根杆，从你能支持的最长杆的最大数量开始，最后用较短的杆来填充。然后重新使用剩余的棒的要求。在这种情况下，第一步是

Rod 1: 3 * 12m + 1 * 4m
recur with [19, 40], [(17, 12), (40, 10), (10, 6), (24, 4)]

你将有相同的切割杆2-6，超过12米的需求在杆7：

Rod 7: 2 * 12m + 1 * 10m + 1 * 6m

现在，您可能需要一个不同的定义“贪婪”。到目前为止，我建议的两项建议是相等的：

1. 以最长的切割杆开始(使用最长的长度)
2. 以最长的切割杆开始，不均匀地分配股票杆的长度(使用最不明显的适合)。

对于第8杆，你将从10米切割(贪婪-1)或6米切割(贪婪-2)开始。

还要注意的是，你可以在每一个单独的杆上重复，只需做一次切割，然后重复使用剩余的长度。

你能从那里拿下来吗？