algorithm - 找出可以从一块木头上切割的最大件数

Question

很抱歉这类问题，但我正在为如下问题寻找一个既定的算法。我找不到名字。问题如下

一把好椅子对工程生产力至关重要。您正在购买木材并尝试自己制作椅子！

家装店有很多长度正好为 L 的木头。根据设计，您需要正好 mm 长度为 a[i] 的木头来制作椅子。

您可以随意切割从家装店购买的木材。例如，您可以将一块长度为 5 的木头切割成长度为 1,4 或长度为 1,3,1

为了完成椅子，您需要在家装店购买最少多少块木头？

实施 CLI 将解决方案构建为 CLI 应用程序，从标准输入接收输入值并将预期输出返回到标准输出。有关详细信息，请参阅本页底部的“命令行应用程序模板”部分。

输入标准输入

a[1] ... a[m] L

1≤m≤10，整数

1≤a[i]≤L，整数

1≤L≤100，整数

输出 在第一行打印制作椅子所需购买的最少木材数量。

I/O 示例 您可以在 test/ 目录中找到预期的输入和输出对。实施时请参考此目录。

输入/输出示例 1

标准输入

3 5 2 10

标准输出

1

如果您购买 1 块长度为 10 的木头并将其切成长度 3、5、2，那么您就有足够的木材来完成椅子。

输入/输出示例 2

标准输入

6 7 6 10

标准输出

3

需要购买 3 块木头。以 [10,10,10]→[6,4,7,3,6,4] 的方式切割，您将有足够的木材来完成椅子。在这种情况下，长度为 4、3、4 的部分将被剩余。

输入/输出示例 3

标准输入

6 7 4 10

标准输出

2

在这种情况下，您可以将一块长度为 10 的木头切割成长度为 6,4 的长度。通过以 [10,10]→[6,4,3,7] 的方式切割，您将有足够的木材来完成椅子。在这种情况下，剩下一段长度为 3 的片段。

我的方法（伪代码）：

int c_number_of_wood_needed ==1

int remaining_piece=最大长度

排序（array_of_pieces）

对于 array_of_pieces 中的每个 PIECE：

 if remaining_piece>=PIECE:
 remaining_piece=remaining_piece-PIECE

 else:
 remaining_piece==Max_length
 c_number_of_wood_needed++
 remaining_piece=remaining_piece-PIECE

标签： algorithmoptimizationmathematical-optimization