Блог пользователя vatsal

Автор vatsal, история, 8 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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