algorithm - 用于切割的最佳组合的算法

Question

输入：我有一个长度为 10m 的母版，我有需要切割 3m、4m、5m 尺寸的产品。

我尝试编写一个算法，它将为我生成下表（最佳长度）：

3m 4m 5m Waste
3  0  0  1
2  1  0  0
1  0  1  2
0  1  1  1
0  2  0  2
0  0  2  0

我了解它是如何工作的，但我不知道如何将其转换为代码。

我需要一些伪代码或帮助（我应该使用递归）吗？

Answer 1

这是一个天真的尝试。在已知范围内进行详尽搜索。

masterLength = 10

print "3m 4m 5m Waste"

for l3m = 0 to floor(masterLenth/3)
{
    for l4m = 0 to floor(masterLength/4)
    {
        for l5m = 0 to floor(masterLength/5)
        {
            usedLength = l3m*3 + l4m*4 + l5m*5
            waste = masterLength - usedLength
            if (waste<3 and waste>=0)
            {
                print l3m,l4m,l5m,waste
            }
        }
    }
}

[编辑] 轻微改进，减少搜索空间。

print "3m 4m 5m Waste"

masterLength = 10
remaining = masterLength

for l3m = 0 to floor(remaining/3)
{
    remaining = remaining-l3m*3
    for l4m = 0 to floor(remaining/4)
    {
        remaining = remaining-l4m*4
        for l5m = 0 to floor(remaining/5)
        {
            waste = remaining - l5m*5
            if (waste<3 and waste>=0)
            {
                print l3m,l4m,l5m,waste
            }
        }
    }
}