Práctica: Reto Dropbox. El Problema de la Dieta

En el sitio web de Dropbox en http://www.dropbox.com/jobs/challenges pueden encontrarse algunos retos de programación.

We get a lot of interest in working at Dropbox but it's not always easy to tell how a person's brain works from a resume. If you're like us, you love a good puzzle. That's why this page is here! It's a great way to share why we love working at Dropbox: innovative thinking, a bit of elbow grease, and some good fun. Who knows? If you knock these puzzles out of the park, we'll have something to talk about when you come in.

Send all submissions to challenges@dropbox.com. The subject line should match the puzzle name. Please send your code (and any associated makefiles), not the executable.

En esta práctica se trata de resolver el problema de la dieta. En el sitio de Dropbox se describe como sigue:

The Dropbox Diet

Of the boatload of perks Dropbox offers, the ones most threatening to our engineers' waistlines are the daily lunches, the fully-stocked drink fridge, and a full-length bar covered with every snack you could want. All of those calories add up. Luckily, the office is also well-equipped with ping-pong, a DDR machine, and a subsidized gym right across the street that can burn those calories right back off. Although we often don't, Dropboxers should choose the food they eat to counterbalance the activities they perform so that they don't end up with caloric deficit or excess.

Help us keep our caloric intake in check. You'll be given a list of activities and their caloric impact. Write a program that outputs the names of activities a Dropboxer should choose to partake in so that the sum of their caloric impact is zero. Once an activity is selected, it cannot be chosen again.

• Input

  Your program reads an integer N (1 <= N <= 50) from STDIN representing the number of list items in the test input. The list is comprised of activities or food items and its respective calorie impact separated by a space, one pair per line. Activity names will use only lowercase ASCII letters and the dash (-) character.

• Output

  Output should be sent to stdout, one activity name per line, alphabetized. If there is no possible solution, the output should be no solution. If there are multiple solutions, your program can output any one of them. Solutions should be non-trivial, so don't send us cat > /dev/null, you smart aleck.

• Examples:

  1. Sample Input	Sample Output
     2 red-bull 140 coke 110	no solution

  2. Sample Input	Sample Output
     12 free-lunch 802 mixed-nuts 421 orange-juice 143 heavy-ddr-session -302 cheese-snacks 137 cookies 316 mexican-coke 150 dropballers-basketball -611 coding-six-hours -466 riding-scooter -42 rock-band -195 playing-drums -295	coding-six-hours cookies mexican-coke

• Puede encontrar dos soluciones al problema escritas en Ruby en el blog de Alan Skorkin. La primera es una solución exhaustiva. La segunda hace uso de Programación Dinámica. Asegúrese que entiende ambas soluciones e intente adaptarlas a su estilo y mejorarlas.