S
Sathya
Hi all
I'm new to Java
Can anyone help me.
Thanks for the help
Sathya
School of Information Technology Semester 2, 2003
HIT3037/HIT7037
Assignment 1
Packing Problem
1 The background
Two-dimensional packing problem is special case of bin packing
problem. Bin
packing arises in a variety of packaging and manufacturing problems.
Suppose that
you are manufacturing object with parts cut from sheet metal, or pants
with parts cut
from cloth. To minimize cost and waste, we seek to lay out the parts
so as to use as
few fixed-size metal sheets or bolts of cloth as possible. Identifying
which part goes
on which sheet in what location is a bin-packing variant called the
cutting stock (or
strip packing) problem. After our objects have been successfully
manufactured, we
will be faced with another bin packing problem, namely how best to fit
the boxes into
trucks to minimize the number of trucks needed to ship everything.
2D Packing Problem (or orthogonal packing)
Input: given a set of rectangles, ri, i=1,…,n
and a rectangular board of given width and undetermined height.
(The input rectangles are given in any non-specified order and
orientation).
Problem: Place all the rectangles on board without overlaps in such a
way that edges
of ri are parallel to x- and y-axes, respectively and the uncovered
part of the board is
minimal. (You can imagine also that the board is a strip of material.
In practical
applications we would rather minimise the height of the strip, after
the all rectangles
are placed onto it).
Solution:
This is an ideal solution (there is no wasted space on the board)
2. The goal of this assignment
You will be given a set of rectangles (objects), ri, i=1,…,n and one
bigger rectangle, a
board, of fixed size w * h. If the solution is optimal, the set of
rectangles will cover
exactly the board. Non – optimal solution will require an exended
board with the
same width w, but greater height h' ,that we will call a strip. The
goal is to find such a
sequence si of placing rectangles one by one on the strip in some
fixed pattern (of
your choice), such that the wasted (uncoverd) part of the optimal
board is minimal.
Let call it the cost function f(si ). If the solution is optimal,
there will be no
uncovered space at the board and f(si ) = 0.
w
h'
Strip
h'
Optimal
board
The sequence of rectangles si is a permutation of all numbers from 0
to n-1, each
number representing a rectangle. All rectangles must be used once and
only once.
The goal of this assignment is to find a reasonably good solution in a
random way. To
find the optimal solution is very hard and is beyond the scope of this
assignment.
However, for each problem presented here, the optimal solution exists.
The outline of the assignment
As an illustration we will use this simple problem:
7 // number of rectangles, each of size (a x b)
3 3 3 2 2 3 5 // side a of rectangle
4 1 3 3 2 1 1 // side b of rectangle
7 x 6 // w*h,size of the board when fully packed (optimal solution)
We can assume that the numbers above can be represented by characters:
one
character represent one unit. So, we can say, that for this problem
the following
rectangles are given:
- the first one:
0 0 0
0 0 0
0 0 0
0 0 0
- the second:
1 1 1
- the third:
2 2 2
2 2 2
2 2 2
etc.
And the strip is:
******''''''''''
******''''''''''
******''''''''''
******'''''''''' - - -> hight,extendable in this direction
******''''''''''
******''''''''''
******''''''''''
The rectangle marked with '*'s represents the optimal board area, and
the right size of
it is exendable (for non-optimal solutions) . You can assume that the
strip is of size 7
x 6*3, that in this case it can be represented by matrix [7][18].
Steps of the algorithm:
1. Generate randomly n numbers, all different. The numbers represent
rectangles
and the sequence – the order in which they will be apply to the board.
For
example, you program generates 4, 1, 3, 5, 2, 0, 6 , and this sequence
is
treated as a proposed solution.
REPEAT for all rectangles:
Determine the next point where the rectangle can be safely inserted
As the first one assume board [0][0] – the top left corner.
Place a rectangle on board without overlaps in such a way that
edges of it are parallel to x- and y-axes.
The first one in our case is 4th (2 * 2):
4 4 * * * *
4 4 * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
END REPEAT
(Before we go to the next step - the point of insertion of the next
rectangle in the example is board [2][0]. I suggest as a selecting
strategy "Left-Down". That is, the candidates for insertion of a
rectangle on board m should be considered in the following order:
m[0,0], m[1,0], m[2,0],…,m[6,0],
m[0,1], m[1,1], m[2,1],…,m[6,1],
m[0,2], m[1,2], m[2,2],…,m[6,2],
m[0,3], .. etc
Other strategies are possible).
You can also apply a rectangle after changing its orientation -you
can decide about it randomly. Instead of placing rectangle 2*3, you
may enter rectangle 3*2 .
2. Display the solution. Normally, it will be not the optimal
solution. For
example, in our case we can finish inserting rectangles with this
arrangement:
4 4 * * 0 0 0 0 ' ' ' ' ' ' ' ' ' '
4 4 * * 0 0 0 0 ' ' ' ' ' ' ' ' ' '
1 5 5 5 0 0 0 0 ' ' ' ' ' ' ' ' ' '
1 * * 2 2 2 ' ' ' ' ' ' ' ' ' ' ' '
1 * * 2 2 2 ' ' ' ' ' ' ' ' ' ' ' '
3 3 3 2 2 2 ' ' ' ' ' ' ' ' ' ' ' '
3 3 3 6 6 6 6 6 ' ' ' ' ' ' ' ' ' '
The cost of this solution we can measure as the number of '*' s on the
board
(the number of uncovered units). In this case your program should
display f(si
) = 8 as a value of the solution. The value of the optimal solution
is, of course,
f(si ) = 0.
3. If this solution is the best so far, save it.
4. Repeat from step 1, unless the optimal solution is obtained or the
maximal
number of repetitions is reached.
3. What to Do
Find the solution for the following problem:
17 // number of rectangles,
each of size (a x b) 4 4 9 3 3 1 5 4 5 7 9 3 2 15 5 10 7 // side a of
rectangles
1 5 4 5 9 4 3 1 5 2 3 13 8 4 4 6 2 // side b of rectangles
20 x 20 // size of the board with optimal solution
Use the method called "generate and test". This method is a variation
of random
search and consists of two steps, usually repeated many times:
• Generation - the program generates randomly a solution in the form
of a
sequence of integers, such as used as an example with 7 rectangles
above:
4, 1, 3, 5, 2, 0, 6 .
All numbers are different, and each number represents a rectangle.
• Test – testing the solution applying rectangles on the board in a
specified
order, using the assumed fixed strategy.
Each solution should be evaluated, and the best saved.
4. Functional and Technical Requiremts
• This program should be implemented in Java as an application
• The application presents a (character-based) menu on screen with the
following functionality:
S – run the program in Steps.
Generate one solution, display it on the screen and evaluate it.
Ask the user if to continue (and to produce the next solution) or to
leave. Always display only the evaluation of the current solution.
T – run the program, generating and Testing n times (after asking the
user for the value of n). At the end of the run, the program
should display the best solution with the its cost (evaluation).
X – eXit the application.
• Because in this problem we have 16 rectangles (more than digits),
for
displaying the board use for rectangles letters A, B, C, D, …, instead
of digits
0, 1, 2, 3, …
• The input data for the problem should be hard coded. However you are
strongly advised to develop your program first for the small problem
(the
example discussed above, with 7 rectangles). After this you can
convert it to
the bigger problem, with 20 rectangles.
• Don't attempt in this assignment to display the solution in a
graphical form
(this will be a part of the next assignment).
• No extra marks will be given for obtaining the optimal solution (
but the
solution shold be a reasonable approximation of the optimum).
5. Due Date
The assignment is due at 8.30am on Monday, 15 September 2003.
The assignment must be placed into the assignment slot of the School
of IT (6th floor
EN building).
(Penalties for late assignments apply as described on the
assignment-facing sheet.)
6. Deliverables
The assignment must be placed in an A4 paper envelope with a completed
assignment
facing sheet on the front
The envelope should contain:
• A 1.44MB floppy disk with all source files and the compiled program
in the
root directory. That includes
o The compiled program (Assign1.class).
o The source codes ( Assign1.java and other classes and files used). A
hard copy of the source code is not required.
• A description of specific algorithm(s) used in the assignment, if it
is different
then specified in this document (eg. the algorithm for placing the
rectangles on
the board)
• Printed evidence of testing (print of the screen with the best
result for
Generate and Test with n = 100).
7. Marking
The assignment is worth 15% of the overall subject assessment.
The assignment will be tested by the tutors in DOS window by typing:
A:\java Assign1
Up to 70% marks will be assigned for the functionality of the
program.
Up to 30% marks will be assigned for quality of programming and
design.
If the Assign1.class is not provided the tutor will compile your
program and 20% will be deducted. If the compilation is
unsuccessful, the student can obtain maximum 30%.
I'm new to Java
Can anyone help me.
Thanks for the help
Sathya
School of Information Technology Semester 2, 2003
HIT3037/HIT7037
Assignment 1
Packing Problem
1 The background
Two-dimensional packing problem is special case of bin packing
problem. Bin
packing arises in a variety of packaging and manufacturing problems.
Suppose that
you are manufacturing object with parts cut from sheet metal, or pants
with parts cut
from cloth. To minimize cost and waste, we seek to lay out the parts
so as to use as
few fixed-size metal sheets or bolts of cloth as possible. Identifying
which part goes
on which sheet in what location is a bin-packing variant called the
cutting stock (or
strip packing) problem. After our objects have been successfully
manufactured, we
will be faced with another bin packing problem, namely how best to fit
the boxes into
trucks to minimize the number of trucks needed to ship everything.
2D Packing Problem (or orthogonal packing)
Input: given a set of rectangles, ri, i=1,…,n
and a rectangular board of given width and undetermined height.
(The input rectangles are given in any non-specified order and
orientation).
Problem: Place all the rectangles on board without overlaps in such a
way that edges
of ri are parallel to x- and y-axes, respectively and the uncovered
part of the board is
minimal. (You can imagine also that the board is a strip of material.
In practical
applications we would rather minimise the height of the strip, after
the all rectangles
are placed onto it).
Solution:
This is an ideal solution (there is no wasted space on the board)
2. The goal of this assignment
You will be given a set of rectangles (objects), ri, i=1,…,n and one
bigger rectangle, a
board, of fixed size w * h. If the solution is optimal, the set of
rectangles will cover
exactly the board. Non – optimal solution will require an exended
board with the
same width w, but greater height h' ,that we will call a strip. The
goal is to find such a
sequence si of placing rectangles one by one on the strip in some
fixed pattern (of
your choice), such that the wasted (uncoverd) part of the optimal
board is minimal.
Let call it the cost function f(si ). If the solution is optimal,
there will be no
uncovered space at the board and f(si ) = 0.
w
h'
Strip
h'
Optimal
board
The sequence of rectangles si is a permutation of all numbers from 0
to n-1, each
number representing a rectangle. All rectangles must be used once and
only once.
The goal of this assignment is to find a reasonably good solution in a
random way. To
find the optimal solution is very hard and is beyond the scope of this
assignment.
However, for each problem presented here, the optimal solution exists.
The outline of the assignment
As an illustration we will use this simple problem:
7 // number of rectangles, each of size (a x b)
3 3 3 2 2 3 5 // side a of rectangle
4 1 3 3 2 1 1 // side b of rectangle
7 x 6 // w*h,size of the board when fully packed (optimal solution)
We can assume that the numbers above can be represented by characters:
one
character represent one unit. So, we can say, that for this problem
the following
rectangles are given:
- the first one:
0 0 0
0 0 0
0 0 0
0 0 0
- the second:
1 1 1
- the third:
2 2 2
2 2 2
2 2 2
etc.
And the strip is:
******''''''''''
******''''''''''
******''''''''''
******'''''''''' - - -> hight,extendable in this direction
******''''''''''
******''''''''''
******''''''''''
The rectangle marked with '*'s represents the optimal board area, and
the right size of
it is exendable (for non-optimal solutions) . You can assume that the
strip is of size 7
x 6*3, that in this case it can be represented by matrix [7][18].
Steps of the algorithm:
1. Generate randomly n numbers, all different. The numbers represent
rectangles
and the sequence – the order in which they will be apply to the board.
For
example, you program generates 4, 1, 3, 5, 2, 0, 6 , and this sequence
is
treated as a proposed solution.
REPEAT for all rectangles:
Determine the next point where the rectangle can be safely inserted
As the first one assume board [0][0] – the top left corner.
Place a rectangle on board without overlaps in such a way that
edges of it are parallel to x- and y-axes.
The first one in our case is 4th (2 * 2):
4 4 * * * *
4 4 * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
* * * * * *
END REPEAT
(Before we go to the next step - the point of insertion of the next
rectangle in the example is board [2][0]. I suggest as a selecting
strategy "Left-Down". That is, the candidates for insertion of a
rectangle on board m should be considered in the following order:
m[0,0], m[1,0], m[2,0],…,m[6,0],
m[0,1], m[1,1], m[2,1],…,m[6,1],
m[0,2], m[1,2], m[2,2],…,m[6,2],
m[0,3], .. etc
Other strategies are possible).
You can also apply a rectangle after changing its orientation -you
can decide about it randomly. Instead of placing rectangle 2*3, you
may enter rectangle 3*2 .
2. Display the solution. Normally, it will be not the optimal
solution. For
example, in our case we can finish inserting rectangles with this
arrangement:
4 4 * * 0 0 0 0 ' ' ' ' ' ' ' ' ' '
4 4 * * 0 0 0 0 ' ' ' ' ' ' ' ' ' '
1 5 5 5 0 0 0 0 ' ' ' ' ' ' ' ' ' '
1 * * 2 2 2 ' ' ' ' ' ' ' ' ' ' ' '
1 * * 2 2 2 ' ' ' ' ' ' ' ' ' ' ' '
3 3 3 2 2 2 ' ' ' ' ' ' ' ' ' ' ' '
3 3 3 6 6 6 6 6 ' ' ' ' ' ' ' ' ' '
The cost of this solution we can measure as the number of '*' s on the
board
(the number of uncovered units). In this case your program should
display f(si
) = 8 as a value of the solution. The value of the optimal solution
is, of course,
f(si ) = 0.
3. If this solution is the best so far, save it.
4. Repeat from step 1, unless the optimal solution is obtained or the
maximal
number of repetitions is reached.
3. What to Do
Find the solution for the following problem:
17 // number of rectangles,
each of size (a x b) 4 4 9 3 3 1 5 4 5 7 9 3 2 15 5 10 7 // side a of
rectangles
1 5 4 5 9 4 3 1 5 2 3 13 8 4 4 6 2 // side b of rectangles
20 x 20 // size of the board with optimal solution
Use the method called "generate and test". This method is a variation
of random
search and consists of two steps, usually repeated many times:
• Generation - the program generates randomly a solution in the form
of a
sequence of integers, such as used as an example with 7 rectangles
above:
4, 1, 3, 5, 2, 0, 6 .
All numbers are different, and each number represents a rectangle.
• Test – testing the solution applying rectangles on the board in a
specified
order, using the assumed fixed strategy.
Each solution should be evaluated, and the best saved.
4. Functional and Technical Requiremts
• This program should be implemented in Java as an application
• The application presents a (character-based) menu on screen with the
following functionality:
S – run the program in Steps.
Generate one solution, display it on the screen and evaluate it.
Ask the user if to continue (and to produce the next solution) or to
leave. Always display only the evaluation of the current solution.
T – run the program, generating and Testing n times (after asking the
user for the value of n). At the end of the run, the program
should display the best solution with the its cost (evaluation).
X – eXit the application.
• Because in this problem we have 16 rectangles (more than digits),
for
displaying the board use for rectangles letters A, B, C, D, …, instead
of digits
0, 1, 2, 3, …
• The input data for the problem should be hard coded. However you are
strongly advised to develop your program first for the small problem
(the
example discussed above, with 7 rectangles). After this you can
convert it to
the bigger problem, with 20 rectangles.
• Don't attempt in this assignment to display the solution in a
graphical form
(this will be a part of the next assignment).
• No extra marks will be given for obtaining the optimal solution (
but the
solution shold be a reasonable approximation of the optimum).
5. Due Date
The assignment is due at 8.30am on Monday, 15 September 2003.
The assignment must be placed into the assignment slot of the School
of IT (6th floor
EN building).
(Penalties for late assignments apply as described on the
assignment-facing sheet.)
6. Deliverables
The assignment must be placed in an A4 paper envelope with a completed
assignment
facing sheet on the front
The envelope should contain:
• A 1.44MB floppy disk with all source files and the compiled program
in the
root directory. That includes
o The compiled program (Assign1.class).
o The source codes ( Assign1.java and other classes and files used). A
hard copy of the source code is not required.
• A description of specific algorithm(s) used in the assignment, if it
is different
then specified in this document (eg. the algorithm for placing the
rectangles on
the board)
• Printed evidence of testing (print of the screen with the best
result for
Generate and Test with n = 100).
7. Marking
The assignment is worth 15% of the overall subject assessment.
The assignment will be tested by the tutors in DOS window by typing:
A:\java Assign1
Up to 70% marks will be assigned for the functionality of the
program.
Up to 30% marks will be assigned for quality of programming and
design.
If the Assign1.class is not provided the tutor will compile your
program and 20% will be deducted. If the compilation is
unsuccessful, the student can obtain maximum 30%.