一维嵌套算法

Question

将1维长度嵌套到预定义的库存长度中的有效算法是什么？

例如,如果您需要以下数量和长度的钢筋,

• 5 x 2米
• 5 x 3米
• 5 x 4米

这些可以从10米棒切割.你如何计算切割10米棒的模式,以便使用最小数量的棒？

另外,如何在算法中加入多个库存长度？

---

我有一些时间来处理这个问题,所以我要写下我是如何解决它的.我希望这对某人有用.我不确定是否可以像这样回答我自己的问题.如果更合适,主持人可以将此更改为答案.

首先感谢所有回答的人.这指出了适当的算法; 切割库存问题.

这篇文章也很有用; "计算最少量的减产废物的切割清单".

好的,关于解决方案.

我将在我的解决方案中使用以下术语;

• 库存:一定长度的材料将被切成小块
• 切割:从库存中切割出的一段材料.可以从同一块库存中取出多个切口
• 废物:在完成所有切割后留在一块原料中的材料长度.

解决问题有三个主要阶段,

1. 确定所有可能的切割组合
2. 确定可以从每个库存中获取哪些组合
3. 找到最佳的切割组合组合.

步骤1

N切口有2 ^ N-1个独特的切割组合.这些组合可以表示为二元真值表.

A,B,C是独特的切口;

A B C | Combination
-------------------
0 0 0 | None
0 0 1 | C
0 1 0 | B
0 1 1 | BC
1 0 0 | A
1 0 1 | AC
1 1 0 | AB
1 1 1 | ABC

具有一些按位运算符的for循环可用于快速创建每个剪切组合的分组.

对于大的N值,这可能非常耗时.

在我的情况下,有多个相同的切割实例.这产生了重复的组合.

A B B | Combination
-------------------
0 0 0 | None
0 0 1 | B
0 1 0 | B (same as previous)
0 1 1 | BB
1 0 0 | A
1 0 1 | AB
1 1 0 | AB (same as previous)
1 1 1 | ABB

我能够利用这种冗余来减少计算组合的时间.我将重复的切割分组在一起并计算了该组的独特组合.然后,我将此组合列表附加到第二组中的每个唯一组合以创建新组.

例如,通过切割AABBC,过程如下.

A A | Combination
-------------------
0 1 | A 
1 1 | AA

将此组称为X.

将X附加到B的唯一实例,

B B X | Combination
-------------------
0 0 1 | A 
      | AA
0 1 0 | B
0 1 1 | BA
      | BAA
1 1 0 | BB 
1 1 1 | BBA
      | BBAA

叫这个组Y.

将Y附加到C的唯一实例,

C Y | Combination
-----------------
0 1 | A 
    | AA
    | B
    | BA
    | BAA
    | BB 
    | BBA
    | BBAA 
1 0 | C
1 1 | CA 
    | CAA
    | CB
    | CBA
    | CBAA
    | CBB 
    | CBBA
    | CBBAA 

此示例生成17个唯一组合,而不是31(2 ^ 5-1).节省了近一半.

确定所有组合后,是时候检查它是如何适合库存的.

第2步

此步骤的目的是将步骤1中确定的切割组合映射到可用的库存大小.

这是一个相对简单的过程.对于每个切割组合,

   calculate the sum of all cut lengths.
   for each item of stock, 
        if the sum of cuts is less than stock length,
            store  stock, cut combination and waste in a data structure.
            Add this structure to a list of some sort.

这将生成有效嵌套剪切组合的列表.存储废物不是严格必要的,因为这可以根据切割长度和库存长度来计算.但是,存储废物会减少步骤3中所需的处理.

第3步

在这一步中,我们将确定产生最少浪费的切割组合.这基于步骤2中生成的有效嵌套列表.

在理想的世界中,我们将计算所有可能性并选择最佳可能性.对于任何非平凡的削减集合,计算它们都需要永远.我们必须满足于非最佳解决方案.有各种算法来完成这项任务.

我选择了一种方法来寻找浪费最少的巢.它将重复此操作,直到所有削减都被计算在内.

从三个列表开始

• cutList:所有必需剪辑(包括重复剪辑)的列表.
• nestList:在步骤2中生成的嵌套列表.这是从最低浪费到最高浪费的排序.
• finalList:最初为空,这将存储将输出给用户的剪切组合列表.

方法

pick nest from nestList with the least waste
  if EVERY cut in the nest is contained in cutList
     remove cuts from cutList
     copy this nest into the finalList
  if some cuts in nest not in cutList
      remove this nest from nestList             
repeat until cutlist is empty

通过这种方法,我设法为一些典型的测试数据总浪费了大约2-4%.希望我能在某个时刻重新审视这个问题并开始实现Delayed列生成算法.这应该会产生更好的结果.

我希望这能帮助其他人解决这个问题.

大卫

Answer 1

实际上,还有一个更具体的问题:割股问题:

切割库存问题是优化问题,或更具体地,整数线性编程问题.它源于工业中的许多应用.想象一下,你在造纸厂工作,你有许多固定宽度的纸卷等待切割,但不同的客户需要不同数量的不同宽度的卷.你是如何切割卷,以尽量减少浪费(剩余的数量)？

这比包装问题更好的原因是因为你试图减少浪费,而不是减少"垃圾箱"的数量.从某种意义上说,垃圾箱包装问题与切割库存问题相反:如何在一定尺寸下将钢材长度重新组装成尽可能少的钢筋？

Answer 2

最低成本箱包装

编辑:这是一个更好的链接:http://en.wikipedia.org/wiki/Bin_packing_problem