Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Dynamic programming solution for bin packing with 3 items of variable size
/* 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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment