14,331,296 members
Rate this:
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
Updated 13-Jan-15 9:23am
v3
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:

## 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 ?

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:

## 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

Top Experts
Last 24hrsThis month
 RickZeeland 263 OriginalGriff 143 Richard Deeming 100 Member 14066596 90 Richard MacCutchan 88
 OriginalGriff 2,313 Maciej Los 1,330 phil.o 958 Richard Deeming 590 Richard MacCutchan 401

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