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.

[gist]5116959[/gist]

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