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#.