2nd Central European Olympiad in Informatics Day 1 - Problem C Fair Sharing

Dynamic Programming Problem

Two brothers, Alan and Bob want to share a set of gifts. Each of the gifts should be given to either Alan or Bob, and none of the gifts can be split. Each gift has a positive integer value. Let A and B denote the total value of gifts received by Alan and Bob, respectively. The aim is to minimise the absolute value of the difference A-B. Write a program which computes the values A and B.

Input data

The first line of the text file INPUT.TXT contains N, the number of the gifts (1<=N<= 100). The rest of the input contains N positive integers, the values of the gifts. Each value is <=200.

Output Data

Write the two integers A and B.

Example input: 7 28 7 11 8 9 7 27

Example output: 48 49

Solution (Yogy Namara) :

Let S be an array to indicate wether a subtotal of S can be achieved with the given values of gifts.

• S[j]=0 if j=0
• S[j]=1..N means that the last item added to
  achieve a subtotal of j is S[j]
• S[j]=None means that a subtotal of j cannot be achieved (yet)

Let G be an array of the value of each gifts. i-th gift will be added to a subtotal of j to achieve a new subtotal of j+G[i] if S[j]<i (a gift cannot be added to a subtotal more than once) and S[j+G[i]]=None (we need some improvements here!)

yogy-n@sby.mega.net.id