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