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.

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