如何找到最大限度地减少砧板损失的最佳算法 [英] How to find the best algorithm for minimizing loss in cutting boards to order

问题描述

我有12米长的木板库存。



如果我订购了一套不同长度的木板，我想计算一下如何减少12米板的最小数量以获得订购的板组，尽可能减少损失。



这应该适用于所有订单，无论如何订购类型。

I have a stock of wooden boards which are 12 meters long.

If I get an order for a set of boards of different lengths, I want to calculate how to cut the minimum number of 12-meter boards to get the set of boards ordered, with as little loss as possible.

This should work with all orders, regardless of the type of ordering.

推荐答案

imho，只有当您需要填写订单的电路板库存包含不同长度的电路板时才会变得非常有趣。如果您的库存总是仅 12米板，这是一个更简单的优化。



您是否开始尝试设计类/数据 - 为此结构，或者开始研究算法，或者在你认为可以适应的地方找到算法？



请出示你的代码。



这个CodeProject文章包含，我相信，你可以适应你的项目的C＃示例：



C# Bin Packing - Cutting Stock Solver [ ^ ]。



此CodeProject文章也可能对您感兴趣：



矩形平铺算法。



有一个开源C＃切割优化izer，Cut Micro，这里：[ ^ ]。

imho, this only becomes really interesting when the stock of boards you have to fill an order with contains boards of varying lengths. If your stock is always only 12-meter boards, it is a much simpler optimization.

Have you started trying to design classes/data-structures for this, or started to work on the algorithm, or found an algorithm somewhere you think you can adapt ?

Please show your code.

This CodeProject article contains, I believe, a C# example you can adapt for your project:

C# Bin Packing - Cutting Stock Solver[^].

This CodeProject article might interest you as well:

Rectangle Tiling Algorithm.

There's an open-source C# cutting optimizer, Cut Micro, here: [^].

这是一个Python解决方案

t = int（raw_input（））

而t> 0：

t- = 1

col = 0

row = 0

m，n = map（int，raw_input（）。split（））

r = map（int，raw_input（）。split（））

c = map（int，raw_input（）。split（））

r.sort（反向） =真）

c.sort（反向=真）

disc = []

cost = 0



while（len（disc）！= m + n-2）：

如果行< m-1和col< n-1：

如果r [row]< c [col]：

cost + = c [col] *（row + 1）

col + = 1

disc.append（c [col-1]）

c [col-1] = 0

else：

cost + = r [row] *（1 + col）

row + = 1

disc.append（r [row-1]）

r [row-1] = 0



if row == m-1：

s = sum（c [col：]）

cost + = s * m

l = len（c [col：]）

disc.extend（范围（l））



如果col == n-1：

s = sum（r [row：]）

cost + = s * n

l = len（r [row：]）

disc.extend（范围（l））

打印成本％（10 ** 9 + 7）

Here's a Python solution
t=int(raw_input())
while t>0:
t-=1
col=0
row=0
m,n=map(int,raw_input().split())
r=map(int,raw_input().split())
c=map(int,raw_input().split())
r.sort(reverse=True)
c.sort(reverse=True)
disc=[ ]
cost=0

while(len(disc)!=m+n-2):
if row<m-1 and col<n-1:
if r[row]<c[col]:
cost+=c[col]*(row+1)
col+=1
disc.append(c[col-1])
c[col-1]=0
else:
cost+=r[row]*(1+col)
row+=1
disc.append(r[row-1])
r[row-1]=0

if row==m-1:
s=sum(c[col:])
cost+=s*m
l=len(c[col:])
disc.extend(range(l))

if col==n-1:
s=sum(r[row:])
cost+=s*n
l=len(r[row:])
disc.extend(range(l))
print cost%(10**9+7)

这篇关于如何找到最大限度地减少砧板损失的最佳算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！