The UVa 10664: Luggage is a typical example of the problems that can be solved using dynamic programming (DP) technique. In fact, after further analysis, this problem can be realized as a special case of Subset-Sum problem, which we have discussed in a recent post.
The following Java code snippet outlines an algorithm using dynamic programming to solve this problem. Notice that the function solveLuggageProblem applies a bottom-up DP to construct dpTable. The boolean value of each dpTable[i][j] implies that whether it is possible to achieve weight j from the weights of 1..i suitcases. In this way, it determines whether halfWeight — the half of the total weights (of the suitcases)– can be derived from using 1..n suitcases, i.e., whether the weights of suitcases can be distributed equally into the boots of two cars.
| import java.io.PrintWriter; | |
| import java.util.Scanner; | |
| class Main { | |
| private final Scanner in; | |
| private final PrintWriter out; | |
| public Main(){ | |
| in = new Scanner(System.in); | |
| out = new PrintWriter(System.out, true); | |
| } | |
| public Main(Scanner in, PrintWriter out){ | |
| this.in = in; | |
| this.out = out; | |
| } | |
| private static int[] readLineAsIntegers(String input){ | |
| String [] ints = input.trim().split(" "); | |
| int [] rets = new int[ints.length]; | |
| for (int i = 0 ;i < ints.length; i++) | |
| rets[i] = Integer.parseInt(ints[i]); | |
| return rets; | |
| } | |
| private String solveLuggageProblem(int[] weights){ | |
| final String _TRUE = "YES"; | |
| final String _FALSE = "NO"; | |
| int totalWeight = getTotalWeight(weights); | |
| if (totalWeight%2 != 0) | |
| return _FALSE; | |
| int n = weights.length+1; | |
| int halfWeight = totalWeight/2; | |
| boolean [][] dpTable = new boolean [n][halfWeight+1]; | |
| // Base case 1: weights = 0 for all n --> True | |
| for(int i = 0;i<n;i++) | |
| dpTable[i][0] = true; | |
| // Base case 2: weights !=0 for all n=0 --> False | |
| for(int i = 1;i<halfWeight+1;i++) | |
| dpTable[0][i] = false; | |
| for (int i = 1; i< n; i++ ){ | |
| for (int j = 1; j< halfWeight+1; j++){ | |
| int w_i = weights[i-1]; // weight of ith item | |
| if(j<w_i) // this item can't be included since its over the limit:j | |
| dpTable[i][j] = dpTable[i-1][j]; | |
| else | |
| dpTable[i][j] = dpTable[i-1][j] || dpTable[i-1][j-w_i]; | |
| } | |
| } | |
| return dpTable[n-1][halfWeight]==true?_TRUE:_FALSE; | |
| } | |
| private int getTotalWeight(int[] weights) { | |
| int totalWeight = 0; | |
| // compute total weight of the bags | |
| for(int indx =0;indx< weights.length;indx++){ | |
| totalWeight += weights[indx]; | |
| } | |
| return totalWeight; | |
| } | |
| public void run(){ | |
| final int T = Integer.parseInt(in.nextLine().trim()); // no of test cases | |
| for (int i = 0 ; i< T ; i++){ | |
| int [] weights = readLineAsIntegers(in.nextLine()); | |
| // result: | |
| out.println(solveLuggageProblem(weights)); | |
| } | |
| } | |
| public static void main(String[] args) { | |
| Main solveLuggageProblem = new Main(); | |
| solveLuggageProblem.run(); | |
| } | |
| } |
Please leave a comment if you have any question regarding this problem or implementation. Thanks.
See Also
SPOJ 97. Party Schedule (PARTY) with F#.
SPOJ 8545. Subset Sum (Main72) with Dynamic Programming and F#.
adilakhter λ 
One thought on “UVa 10664. Luggage”