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.
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/04/2024 21:09:58 (i1).
Desktop version, switch to mobile version.
Supported by
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).