想咨询一个生产排产算法问题

[ahaxzh]

1 、有一卷无限长的布匹，布宽约 5.55 米（我们且称为原始布 X ）。

2 、根据客人的订单，需要将这 5.55 米宽的布匹分成宽度各异的小的布匹卷（ y1 、y2 、y3.....，相加小于等于 5.55 米）。

3 、每个小卷的宽度（ Yi ）是订单中给定的，每个小卷的长度是固定的 150 米。

4 、切割布匹需要使用多把机械剪刀，比如根据订单

可以将 5.55 米的原始布 X 分成 1.2 米、1.2 米、1.5 米、1.55 米、0.1 米（损耗），

这样会同时布置四把机械剪刀，但更换剪刀间距（或者增加、取下）需要一定的成本δ，所以尽可能在少换刀的情况下对 原始布 X 进行剪裁。

5 、如果订单的小布匹卷相加起来宽度小于 5.55 米，可以搭配切一些比较好卖的小布匹卷 Ui （如 1.5 米宽、1.2 米宽等）。

6 、在此基础上如何最节约不浪费的剪裁布料。

输入： X(原始布的宽度)

Yi*n （订单中小布卷的宽度 以及 每种宽度需求数量 n ）

Ui (搭配裁剪的小布卷)

输出就是裁剪的方案组别。

值得注意的事情，“5.55 米的原始布 X 分成 1.2 米、1.2 米、1.5 米、1.55 米、0.1 米（损耗）”，这里是需要 4 把机械剪刀的！而不是三把~

最初我拿到这个之后第一反应是能做，使用多重动态规划就行了，可是我发现根本没有那么简单，真实案例中还涉及到布匹的厚度，原始布的总长度等奇形怪状的因素。

如果实在不行可以先忽略换刀的情况。

[sillydaddy]

> Ui (搭配裁剪的小布卷)

Ui 的含义不明确，下标 i 代表什么？每个 Yi 对应一个 Ui ？按我的理解

输入
X （原始布的宽度）
Yi*Ni，i∈[0, m] （订单中小布卷的宽度种类共有 m 中，宽度为 Yi，该宽度需求数量为 Ni ）
Uj，j∈[1, n]（搭配裁剪的小布卷的宽度种类有 n 种，Uj 为小布卷宽度）

是这样理解吗？

有个问题，用于搭配的小布卷，如果种类多于一个，需要怎样搭配呢？比如最后一段 150 米长的布匹，剩余布料宽为 4 米，那可以制作搭配的小布卷：2 个 1.5 米的，或者 3 个 1.2 米的，怎么选择呢？选布料浪费最少的吗？

[ahaxzh]

@sillydaddy 是的，可以这么理解。
关于 Ui，是给定的一组比较好卖的布的宽度，如你所说 1.2 、1.5 这种。