Click here to Skip to main content
14,331,296 members
Rate this:
Please Sign up or sign in to vote.
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
Updated 13-Jan-15 9:23am
v3
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.:)
Rate this:
Please Sign up or sign in to vote.

Solution 1

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: [^].
   
Rate this:
Please Sign up or sign in to vote.

Solution 2

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)
   
v2

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




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100