时间戳

首页 > 解决方案 > 类似于切割库存但不完全

python - 类似于切割库存但不完全

问题描述

我读过关于切割库存问题的文章，但这有点不同。请你指导我一些资源。有装箱、切料...

我们有不同型号的订单，以及最大尺寸的机器来生产它。

变体为 X、S、XL、L，订购数量为 100、40、40、80

X > 100

S > 40

XL > 40

长 > 80

说，机器宽度是6

这意味着，我们可以将 6 个不同的变体放在一起并生产它。

我们可以放 2 X,1 S,1 XL,2 L ，这意味着如果我们生产 50 次，输出是：

X > 100（0 浪费）

S > 50 (10 废物)

XL > 50（10 个废品）

L > 100（20废）

共产生 300 个废物中的 40 个废物。

另一种减少浪费的方法是创造两种不同的变化。我们可以放 4 X,2 S 生产 25 次，有 10 个废料再做另一个设置，放 2 XL,4 L 生产 20 次，没有废料。总共有 10 个废物，我们在 2 个设置中处理了这个生产。

由于设置有价格，我们更喜欢第一个设置，或者根据数量，我们可以选择第二个。

我读过关于切割库存的文章，它看起来与这个相似，但能够在不同设置之间划分数量，这具有更大的优化潜力，因此更复杂。

我想了想，也没有可靠的解决方案，如果这个问题在文学中有任何位置，你能不能至少告诉我关键词，以便我搜索它？

谢谢。

注意：我知道基本的数学和良好的 python 编程语言。

标签： pythonalgorithmdynamic-programmingknapsack-problembin-packing

解决方案

我建议通过 A* 搜索来解决这个问题，寻找最快和最低成本的方法来完成剩下的 0。

可能对您来说新的数据结构是优先级队列，您可以通过https://docs.python.org/3/library/heapq.html获得它，访问节点的字典，以及一点点逻辑。诀窍是你可以随意放入可能的部分解决方案，它们会按照成本最低的顺序出现，然后是完成的最远。

这是主要逻辑的未经测试的代码。

# There should be 84
configs = generate_list_of_machine_configurations(variants)
# Our priority queue
upcoming = [(0, sum(quantities), quantities, None]
seen = set()
while (len(upcoming)):
    (waste, _, quantities, path) = heapq.heappop(upcoming)
    if tuple(quantities) not in seen:
        if all_zeros(quantities):
            return path # ANSWER IS FOUND HERE

        seen.add(tuple(quantities))
        for config in configs:
            for count in range(max(quantities)):
               (new_quantities, wasted) = apply(quantities, config, count)
               new_path = [(config, count), path]
               if all_zeros(new_quantities):
                   heapq.heappush(upcoming, (
                       waste + wasted, 0, new_quantities, new_path))
               else:
                   heapq.heappush(upcoming, (
                       waste + wasted + cost_of_config_switch,
                       sum(new_quantities), new_quantities, new_path))

推荐阅读