vatsal's blog

Approach for Uva 624
By vatsal, history, 8 years ago, In English

How can I approach Uva 624 Uva 624 . Simplified Problem Statement: A set S={a,b,c,x,y} is given and a target sum is given so we have to find the elements which sums to the target sum or even very close to it. I think its a DP problem but I don't know how to approach it so giving the algorithm and explanation would be very nice.

  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can try all 2^n posibilities. If you want the optimal solution (the best I know is n^2 with DP) you can do a subset sum. Once you have the DP table filled, you need to traverse it, and find the element wich is closer to the lenght of the CD (I mean, calculate the absolute difference with the CD lenght, and the answer will be the combination of tracks with lesser difference).

→ Reply