. .

## Packing Boxes - a greedy algorithm

 ```/********************************************* == Holiday Packages - a Simulation == This program SIMULATES the problem of packing heavy objects into boxes, which will then be shipped (perhaps by DHL). There are 10 objects of various weights, e.g. 20 25 13 8 9 14 12 29 35 21 This is a very CHEAP simulation. The user must type the POSITION of the object to put it into the box. For example, you could fill a box EXACTLY full by taking items #1 , #2 , and #6 making 50 kg exactly. The goal is to use as few boxes as possible, as each box must be paid for. Assume it is being shipped with a fixed price per box, say 40 EU each. Then every box you save means you saved 40 EU. *************************************************/ public class PackBoxes { int[] nums = new int; int boxes = 0; public PackBoxes() { output("== Packing Boxes ==\n" + "Each box can hold 50 kg. \n" + "You must put objects (right) \n" + "into boxes, but don't exceed 50 kg.\n" + "Use as few boxes as possible." ); makeNums(); do { fillBox(); } while (checkDone() == false); output("You used " + boxes + " boxes"); System.exit(0); } public void fillBox() { boxes = boxes + 1; int total = 50; int contents = 0; int choice = -1; do { String ask = input(allNums() + "\nChoose a position in the list (nothing to PACK):"); if (ask.length() == 0) { choice = -1; } else { choice = Integer.parseInt(ask); } if (choice >= 10) { output("Illegal position"); } else if (choice < 0) { output("Packing the box now."); } else if (nums[choice] <= total) { contents = contents + nums[choice]; total = total - nums[choice]; nums[choice] = 0; } else { output("That is too heavy for this box."); } } while (choice >= 0); output("That box contains " + contents + " kg."); } public void makeNums() { nums = random(5, 35); nums = random(5, 35); nums = random(5, 35); nums = random(5, 35); nums = random(5, 35); nums = random(5, 35); nums = random(5, 35); nums = random(5, 35); nums = random(5, 35); nums = random(5, 35); } public int random(int smallest, int largest) { return (int) (Math.random() * (largest - smallest + 1) + smallest); } public String allNums() { return (" " + nums + " " + nums + " " + nums + " " + nums + " " + nums + " " + nums + " " + nums + " " + nums + " " + nums + " " + nums); } public boolean checkDone() { if (nums > 0 || nums > 0 || nums > 0 || nums > 0 || nums > 0 || nums > 0 || nums > 0 || nums > 0 || nums > 0 || nums > 0) { return false; } else { return true; } } public static void main(String[] args) { new PackBoxes(); } public String input(String prompt) { return javax.swing.JOptionPane.showInputDialog(null, prompt); } public void output(String message) { javax.swing.JOptionPane.showMessageDialog(null, message); } java.awt.Font bigFont = new java.awt.Font("Verdana", java.awt.Font.BOLD, 24); int useBigFonts = bigFonts(); public int bigFonts() { javax.swing.UIManager.put( "OptionPane.messageFont", new javax.swing.plaf.FontUIResource(bigFont) ); javax.swing.UIManager.put( "OptionPane.buttonFont", new javax.swing.plaf.FontUIResource(bigFont) ); return 0; } } ```

### Optimization - preferably Automatic

This program doesn't actually do anything automtically, but it points up the NEED for automation.
When you run the program, you must choose several items that will fit in a box for a total weight
of 50 kg or less.  Then pick items to pack into a second box.  Continue until all the items are
in a box.  The goal is to use as few boxes as possible - don't pack one item in each box!

When you are doing this, think about your own thinking.  What are you thinking when you try
to choose an optimal set of items?  Do you just start with the first item and second item and
then look for another that fits?  Or do you just around in the list, looking for a set that make
exactly 50?

### Programming Practice

```/***********************************************
(0) Play the game (oops, RUN the SIMULATION) a few times
to see how it works.  Then make the changes listed below.

(1) Change MAKENUMS so it uses a LOOP instead
of 10 separate commands.

(2) Change MAKENUMS so it uses bigger numbers -
between 20 and 100.  Then change the limits
on a box to 100 kg.  Then the game is more challenging.

(3) Change the program to use 12 objects instead of 10.
You will need to change several parts of the program.

(4) Write a method called HELP.  If the user types 99,
the HELP method should run and SUGGEST an item
that could still fit in the box.

(4) Write a method called HELP.  If the user types 99,
the HELP method should run and SUGGEST an item
that could still fit in the box.  What is the
ALGORITHM for making a good suggestion?

(5) Write a GREEDY automatic algorihtm.  It works like this:
put the first item in the box
if there is still room, put the next item in
if there is still room, put the next item in
continue until the next item won't fit
once you reach this point, search through the rest
of the array for a small enough item
continue until no more items fit in the box
Pack the box then repeat, starting at the first
non-zero item.

(6) Write a BETTER auto method.  This time, the program
searches for any PAIR of numbers that fill the box
EXACTLY.  Then pack them in the box and repeat.
If there is no pair that fills the box, then
try to find 3 items that will fill the box EXACTLY.
If it's not possible to fill the box exactly,
then try to fill it to MAX-1.  Then try MAX-2, etc.
The goal is to make the box as full as possible.

This problem is an example of ARTIFICIAL INTELLIGENCE.
This is non-trivial, especially if you want a"good" answer,
or perhaps even "the best" answer.

This is known by two different names for slightly different
versions of the problem:

(1) Knapsack problem - given a knapsack (backpack) and a
set of weights, find a combination of weights that
fills the knapsack exactly.  This can be used as
the basis of an ENCRYPTION algorithm, but was shown
to be "breakable".

(2) Partition problem - divide a set of weights into 2 or
3 or more "partitions" that all contain the same total -
or, more realistically, divide the weights into
some number of groups that are as evenly distributed
as possible.

These problems are "AI hard" problems, requiring far toomuch searching.

************************************************/
```