求解最佳分配的算法问题

时间:2021-01-23 04:21:34
这是个服装裁剪问题, 有个集合(n0...nx)x最多给到8,给出一个最大值X,X为整数不超过20,

求(m0...mx)的迭代分配多次后集合(n0...nx)全为0,每次(m0...mx)的取值关系为等比关系,等比值的和小于X,在这基础上考虑二个优先,第一:让(m0...mx)取值大于0的个数越多越好,从而获得最佳的的分配;第二:让迭代的次数越少越好,可以提高效率。

如果对裁剪问题不太明白的可以参考下评论中的背景资料。

例如:

                   (200,400,500,850,740,420)      X=6   
第一次取值   (0,  400,  400, 800, 400, 400)      6     
                    (200,0  ,100,50 ,340,20)
第二次取值   (200,  0,  100,  0,  300,  0)          6     
                     (0,  0,  0,  50, 40, 20)          
第三次取值   (0,  0,  0,  40,  40, 20)                 5    
                     (0,  0,  0,  10, 0,   0)
第四次取值   (0,  0,  0,  10,  0,   0)                 1   
                     (0,  0,  0,  0,  0,   0)
经过四次尝试后集合数据清零。

这个是不是最佳没求证,但思路是这样子的,求算法怎么解?


有朋友问这个题的背景,其实就是这题怎么来的,实际生产是我们的老师,这个题目来源于服装生产。
服装订单下单就是我的集合(xs,s,m,l,xl,xxl)这些码数的订单数就是我的(n0...nx),所以我会说x取值不超过8,超过8的衣服都不是人穿的;
做纸样的师傅一看这衣服布料再看这衣服的大小就确定了一张布上可以裁多少件衣服,就是X一个输入性定值;
现在就是要把订单数开裁了知道了最大件数就开始分配了这X件衣服中xs\s\m\l\xl\xxl分别占用多少比值,比值就是(m0...mx);
再计算一张唛架纸(可复制相同唛架纸,所以可以直接计算400层的布,实际上400层布要分多床进行裁剪)上最多能拉多少层布,这个就是L;
最后经过多层计算,就可以把订单数分配完。(注在实际中先估计一个L值,再去分配比值,人工计算时会先比对下订单数量,所以L值在3到4次的简单计算中给出来,也有可能订单数比较整的一下就出来了)

(m0...mx)* L就是上面提出的(m0...mx)要是等比关系,这个一定是等比的。


以下是实际生产中的更复杂的条件考虑,仅仅说下,暂时对上面的不产生影响!

实际情况中如果人工计算时发现分配的数多或少了一点,看订单数量,如(-2~5)之间,客户允许工厂进行增加或减少一个小点的百分比是没问题,工厂考虑更多的是增加百分比;还有看款式如果简单款式,小码数量少了点而大码数多了点,可以通过大码改小码进行分配,这个计算机就完全没办法了。
实际上,这个只是单色混码的分配,还有多个颜色下单进行混码分配的时候,要考虑上面的分配比值也可以在其它颜色下复用,复用的比值次数越多越好。
背景介绍完了。