Sketchy Polytopes

## Problem: The Dropbox Diet

Dropbox posed the following problem on their website:

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.

##### Sample Input
2
red-bull 140
coke 110

##### Sample Output
no solution

12
free-lunch 802
mixed-nuts 421
orange-juice 143
heavy-ddr-session -302
cheese-snacks 137
mexican-coke 150
coding-six-hours -466
riding-scooter -42
rock-band -195
playing-drums -295

coding-six-hours
mexican-coke


Here is a linear program in Octave that solves it:

c = [1 1 1 1 1 1 1 1 1 1 1 1];
a = [802 421 143 -302 137 316 150 -611 -466 -42 -195 -295];
b = [0]';
lb = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
ub = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1];
ctype = "S";
vartype = "IIIIIIIIIIII";
sense = -1; % maximize

param.msglev = 3;
param.itlim = -1;

[xmin, fmin, status, extra] = glpk (c, a, b, lb, ub, ctype, vartype, sense, param)