CS323 - Dynamic Programming Homework

Problem description

You are given the following items:
You have available an infinite supply of bins (boxes) of Capacity C
Assignment:

Note:

I have illustrated in class using many examples how to develop non-recursive dynamic programming program

You first solve the problem using a recursive solver (this algorithm will give you an idea on how to compute the value iteratively)
Then define the table (array) to store the values of the different solutions
Use the recursive solver to write the code for the base case(s)
Use the recursive solver to write the code for the other cases
Make sure you iterate "in the direction" of the data flow.

Hint on how to develop the recursive solution --- part 1

Define:

M(k₁, k₂, k₃, resCap) = the minimum # bins needed to pack:
when you have a residual capacity of resCap left in the current bin that you are using.

Example:

Suppose:
M(0,0,1,10) = 1,
because packing
when you have a residual capacity of 10 left in the current bin that you are using, you need 1 bin (use your current bin)
M(0,0,1,5) = 2,
because packing
when you have a residual capacity of 5 left in the current bin that you are using, you need 2 bins (the item does not fit in your current bin, so you need another bin)

Hint on how to develop the recursive solution --- part 2

General idea:

Recursive method to compute: M(k₁, k₂, k₃, resCap)

Here is the logic for packing a type 1 item into the current bin (with residual capacity resCap) that we are using:

If the item fits in the current bin, we pack the item into the current bin (the residual capacity of the current bin is reduced by s₁) and delegate the following smaller problem:
The original problem is solved using the returned solution as follows:
You will use the same number of bins as answer because the item 1 will fit
(because you deducted s₁ from the residual space before you delegated the problem)
If the item does NOT fit in the current bin, we pack the item into a new bin
The residual capacity of the new current bin is equal to C − s₁
We then delegate the following smaller problem:
The original problem is solved using the returned solution as follows:
You will now use one more bin as answer because the item 1 did not fit
(because you started a new bin before you delegated the problem)

Note:
You need to repeat this solution procedure for all 3 types of items
Therefore, you will obtain 3 possible solutions, let's call them:
The value of M(k₁, k₂, k₃, resCap) = minimum(my_sol₁, my_sol₂, my_sol₃)

Skeletal program

Here's a skeletal program that help you get started:

import java.util.*; public class BinPacking { /* ----------------------------------------------------------- solveBP(k1, s1, k2, s2, k3, s3, resCap, Cap): returns the min # bins needed to pack: k1 items of size s1 k2 items of size s2 k3 items of size s3 using bins of capacity Cap when the current bin has a residual capacity of "resCap" ----------------------------------------------------------- */ public static int solveBP(int k1, int s1, int k2, int s2, int k3, int s3, int resCap, int Cap) { // Write you (recursive) solution here } public static void main(String[] args) { int n1, n2, n3; int s1, s2, s3; int Cap; int out; Scanner in = new Scanner(System.in); System.out.print("Size of item 1 = "); s1 = in.nextInt(); System.out.print("Number of item 1 = "); n1 = in.nextInt(); System.out.print("Size of item 2 = "); s2 = in.nextInt(); System.out.print("Number of item 2 = "); n2 = in.nextInt(); System.out.print("Size of item 3 = "); s3 = in.nextInt(); System.out.print("Number of item 3 = "); n3 = in.nextInt(); System.out.println(); System.out.print("Capacity of the bin = "); Cap = in.nextInt(); if ( s1 > Cap || s2 > Cap || s3 > Cap ) { System.out.println("Input error: some item's size is too large for bin"); System.exit(1); } out = solveBP(n1, s1, n2, s2, n3, s3, Cap, Cap); System.out.println("Min # bins needed = " + out); } }

It reads n₁, s₁, n₂, s₂, n₃, s₃, and C, invoke the method solveBP(n1, s1, n2, s2, n3, s3, Cap, Cap) to find the solution.

You need to write the solveBP() method

Obtain the skeletal program:

Testing your solution
- You can run the following command to get the correct answers:
  Cut and paste the entire line into a console window to run it.

Warning: deduction for non-compliance

Repeat: your solution must be non-recursive (true dynamic programming)
If your solution is recursive (even if it is correct), you will receive a 20 pts deduction for this assignment

Advice:

First, develop a recursive solution and test it thoroughly (compare answers by running against my program)
Turn the recursive solution in when you're done !!!
(Because you can overwrite it later if you finish the non-recursive solution)
When you turn in a new program file, it will over-write the old turnin file that was turned in previously.
When your non-recursive program is completed (and tested). turn the non-recursive solution in

Turn in

Turn in your program using the following command:

/home/cs323000/turnin BinPacking.java hw6