How to find the best algorithm for minimizing loss in cutting boards to order

Question

3.00/5 (1 vote)

See more:

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.

Posted 13-Jan-15 6:41am

GeekGirl90

Updated 13-Jan-15 9:23am

BillWoodruff

v3

Add a Solution

Comments

CHill60 13-Jan-15 12:54pm

What have you tried? How are you storing the information about the boards?

GeekGirl90 16-Jan-15 13:09pm

I have tried to write a solution myself, but I'm not sure that I have the best solution. I try to cat the longest board, and then check can I use the rest. For example if I should cut 3 boards of 8m, 4 from 7 and 4 from 3m, I first cut 3 boards of 8. Then i have leftover wich have 4m. I cut that leftovers to get 3 boards from 3m. Than I cut 4 boards to get borars size 7m. Leftovers are long 5m. That means that i should cut one of them to make one more size 3m, which is missing. But I hope that there is a better soltion, and I'm just searching for it. The information about boards i can store in database or in some file...

Richard MacCutchan 13-Jan-15 13:10pm

This is an obvious homework question, and can be solved by a bit of research and some hard work. Which is what your professor will expect you to do.

ZurdoDev 13-Jan-15 14:25pm

Sounds like a cool program. What is your question?

GeekGirl90 16-Jan-15 13:12pm

My question is how to solve the problem in the best way and with minimum losses .. I just need a good idea.:)

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

BillWoodruff · Answer 1 · 2015-01-13T09:21:00

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: [^].

Member 12064038 · Answer 2 · 2015-10-16T03:32:00

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)

How to find the best algorithm for minimizing loss in cutting boards to order

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0