优化的切割解决方案（背包/垃圾桶包装）C＃ [英] optimized cutting solution (knapsack/bin packing) C#

问题描述

我需要以下解决方案，并一直在努力使其正确。我也搜索过高低，但找不到任何可以使用的东西。也许我不能很好地理解我自己的问题。



我需要能够以编程方式找到切割绳索/管道长度的最佳方法。

以下是场景：

我有以下库存：3 X 4.7m 5 X 7.4m 3 X 11.2m 4 X 9.8m（这些是我目前的绳索长度有货）



我需要为订单削减以下长度：2 X 3m 4 X 1.2m 1 X 6m 2 X 5.4m





我已经开始使用一个公式，将我的所有库存分解为1 X长度（意味着如果我有3 X 4.7mi显然有1 X 4.7m和1 X 4.7m和1 X 4.7m）我对订单需要切割的长度做了相同的工作。

我已经开始将最长切割长度与最短切割长度相匹配库存长度，如果可以，我需要增加另一个长度，如果有足够的绳索剩余，然后进入下一个库存项目。

基本上纸上我能够工作ev如何切割这些，然后看看哪个选项浪费了最少量的绳索（我已经计算了我已切割的剩余部分和最少的剩余物或废物是最佳选择）的可能性和组合。



现在我的问题是我需要用代码执行此操作并且似乎无法正确执行此操作，尤其是每个订单的剪切长度和数量都是动态的。



如果有人可以指出我正确的方向或协助我为此编写代码，我将不胜感激。



问候，

Ben

Hi,
I need the following solution and have been battling to get it right. I have also searched high and low but could not find anything that I could use. Perhaps I am not understanding my own problem well enough.

I need to be able to programmatically find the best way to cut lengths of Rope/Pipe.
Here is the scenario:
I have the following lenthgs in stock: 3 X 4.7m 5 X 7.4m 3 X 11.2m 4 X 9.8m (these are lengths of rope that I currently have in stock)

I need to cut the following lengths for an order: 2 X 3m 4 X 1.2m 1 X 6m 2 X 5.4m


I have started of with a formula that will break down all my stock in to 1 X something lengths (meaning if I have 3 X 4.7m i obviously have 1 X 4.7m and 1 X 4.7m and 1 X 4.7m) I did the same for the lengths i need to cut for the order.
I have proceeded to match the longest cut length to the shortest stock length, if it can be done I need to add another length if there are enough rope remaining before going on to the next stock item.
Basically on paper I was able to work out every possibility and combination of how to cut these and then see which option wastes the least amount of rope ( i have calculated the left overs from the pieces I have cut and the least amount of leftovers or waste was the best option).

Now my problem is that I need to do this with code and cannot seem to get it right especially the fact that the cut lengths and amounts are dynamic per order.

If someone could please point me in the right direction or assist me with writing the code for this it would be much appreciated.

Regards,
Ben

推荐答案

1）请求所需的绳索数量不应该是多少您的库存中提供了所需的长度。

2）这种类似的最简单的算法可能是：

    a）按要求对所请求的项目进行排序降价。

    b）每一个您已分拣的所需物品

       i）使用尽可能最短的库存绳索完成订单。

        ii）将步骤i中使用的库存绳索的未使用部分返回到您的库存中，以便其他请求可以使用它。

        iii）冲洗并重复直至完成。

1) It should never matter how many pieces of rope are being requested, just that all the lengths requested are available in your stock.
2) The simplest algorithm for something like this could be:
   a) Sort your requested items by length descending.
   b) For each of your sorted requested items
      i) Fullfil the order using the shortest stock rope possible.
      ii) Return the unused portion of the stock rope used in step i back into your inventory so that another request can make use of it.
      iii) Rinse and Repeat until complete.

嗨Ben，

我刚刚发布了一个应用程序来解决您的问题。

您可以在 C＃Bin Packing - Cutting Stock Solver [ ^ ]



问候



Alberto Montibelli

Hi Ben,
I've just posted an application to solve your problem.
You can find it at C# Bin Packing - Cutting Stock Solver[^]

Regards

Alberto Montibelli

这篇关于优化的切割解决方案（背包/垃圾桶包装）C＃的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！