Dynamic programming solution for bin packing with 3 items of variable size

3-item-bin-packing.java

/* THIS CODE IS MY OWN WORK, IT WAS WRITTEN WITHOUT CONSULTING A TUTOR OR CODE WRITTEN BY OTHER STUDENTS -HYO BYUN*/
import java.util.*;
public class BinPacking {

   /* -----------------------------------------------------------
      SolveBP(k1, s1, k2, s2, k3, s3, Cap):
  	NOTE DOESN"T USE RESIDUAL CAP, USES FILLED CAP
          returns the min # bins needed to pack:

		k1 items of size s1
		k2 items of size s2
		k3 items of size s3
		N
      ----------------------------------------------------------- */
	public static int solveBP(int k1, int s1, int k2, int s2, int k3, int s3, int Cap) {
		int[][][][] dp= new int[k1+1][k2+1][k3+1][2];
		dp[0][0][0][0]=1;
		if((k1==0 && k2==0 && k3==0) || (s1==0 && s2==0 &&s3==0) )
			return 0;
		for(int i=0;i<=k1;i++) 
			for(int j=0;j<=k2;j++)
				for(int k=0;k<=k3;k++) {
					if(i==0 && j==0 && k==0)
						k=1; //skip base
					int sol[][]= new int[3][2]; // first dim = item type, second dim = 4th dim of dp matrix.
					boolean extraBin[] = new boolean[3];
					//Start computing candidate solutions - incomplete computation
					sol[0][0] = (i==0) ? Integer.MAX_VALUE-5 : dp[i-1][j][k][0];
					sol[1][0] = (j==0) ? Integer.MAX_VALUE-5 : dp[i][j-1][k][0];
					sol[2][0] = (k==0) ? Integer.MAX_VALUE-5 : dp[i][j][k-1][0];
					//Needs extra bin?
					extraBin[0] = (i!=0 && dp[i-1][j][k][1]+s1 >Cap) ? true : false;
					extraBin[1] = (j!=0 && dp[i][j-1][k][1]+s2 >Cap) ? true : false;
					extraBin[2] = (k!=0 && dp[i][j][k-1][1]+s3 >Cap) ? true : false;
					//Finish computing candidate solutions
					for (int l=0;l<3;l++)
						sol[l][0]=extraBin[l] ? sol[l][0]+1 : sol[l][0];
					sol[0][1] = (i==0 || extraBin[0]) ? s1 : dp[i-1][j][k][1]+s1;
					sol[1][1] = (j==0 || extraBin[1]) ? s2 : dp[i][j-1][k][1]+s2;
					sol[2][1] = (k==0 || extraBin[2]) ? s3 : dp[i][j][k-1][1]+s3;
					//Find minimum of 3 candidates, if nBins equal, take one with lower fill
					for(int l=0;l<3;l++)
						if(l==0 || sol[l][0] < dp[i][j][k][0] || (sol[l][0] == dp[i][j][k][0] && sol[l][1]< dp[i][j][k][1]) ) {
							dp[i][j][k][0] = sol[l][0];
							dp[i][j][k][1] = sol[l][1];
						}
				}
				return dp[k1][k2][k3][0];
   }


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

      System.out.println("Min # bins needed = " + out);
   }

}