algorithm- 棒切割算法
algorithm- Rod cutting algorithm
给定 n 根杆，比如 m 米，我们希望进行以下操作：
- 切割长度为m1的n1根棒
- 切割长度为m2的n2根棒
- .....
解决这个问题的贪婪方法是什么？
我试过标准的回溯问题，但这很慢。能不能有一个贪心的方法来解决这个问题？
另外我注意到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。这意味着问题可以解决，但我没有得到我贪婪方法的线索。
一种贪婪的方法是在每次迭代中切割一根杆，从您可以支持的最长杆的最大数量开始，最后填充较短的杆。然后重复剩余杆的剩余要求。这种情况下的第一步是
Rod 1: 3 * 12m + 1 * 4m
recur with [19, 40], [(17, 12), (40, 10), (10, 6), (24, 4)]
对于 2-6 号杆，您将有相同的切割，运行 在 7 号杆上需要 12 米：
Rod 7: 2 * 12m + 1 * 10m + 1 * 6m
现在，您可能需要 "greedy" 的不同定义。我提出的两个到目前为止是等价的：
- 从最长的开始cut-rod（使用最长的）
- 从最长的 cut-rod 开始，它不能平均划分 stock-rod 的长度（使用最不明显的拟合）。
对于 8 号杆，您将从 10m 切割 (greedy-1) 或 6m 切割 (greedy-2) 开始。
另请注意，您可以在每个单独的杆上重复进行，只需进行一次切割，然后重复剩余长度。
你能从那里拿走吗？
给定 n 根杆，比如 m 米，我们希望进行以下操作：
- 切割长度为m1的n1根棒
- 切割长度为m2的n2根棒
- .....
解决这个问题的贪婪方法是什么？
我试过标准的回溯问题，但这很慢。能不能有一个贪心的方法来解决这个问题？
另外我注意到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。这意味着问题可以解决，但我没有得到我贪婪方法的线索。
一种贪婪的方法是在每次迭代中切割一根杆，从您可以支持的最长杆的最大数量开始，最后填充较短的杆。然后重复剩余杆的剩余要求。这种情况下的第一步是
Rod 1: 3 * 12m + 1 * 4m
recur with [19, 40], [(17, 12), (40, 10), (10, 6), (24, 4)]
对于 2-6 号杆，您将有相同的切割，运行 在 7 号杆上需要 12 米：
Rod 7: 2 * 12m + 1 * 10m + 1 * 6m
现在，您可能需要 "greedy" 的不同定义。我提出的两个到目前为止是等价的：
- 从最长的开始cut-rod（使用最长的）
- 从最长的 cut-rod 开始，它不能平均划分 stock-rod 的长度（使用最不明显的拟合）。
对于 8 号杆，您将从 10m 切割 (greedy-1) 或 6m 切割 (greedy-2) 开始。
另请注意，您可以在每个单独的杆上重复进行，只需进行一次切割，然后重复剩余长度。
你能从那里拿走吗？