New Years Resolution

There are three types of "macronutrients": protein, carbohydrates, and fat. There are $$N$$ food items ($$1 \leq N \leq 20$$). Each food item $$i$$ has $$P_i, C_i,$$ and $$F_i$$ units of protein, carbohydrates, and fat (respectively). There is a goal amount $$P$$,$$C$$, and $$F$$ for how much of each type of nutrient you would like to consume today (exactly). Is there a subset of food items that you can choose to get exactly the right amount of each?
  1. Subset sums problem
  2. $$N$$ is small
  3. Bitmask DP

If there was only one macro-nutrient this would exactly be the classic "Subset Sums" problem: Given a list of integers $$A_1, A_2, ..., A_N$$ and a goal value $$V$$, find a subset of the integers that add to exactly $$V$$.

There are three nutrients, so this is a bit harder, but the problem can be solved in a similar way. (If you have never heard of the Subset Sums problem, I encourage the reader to Google it to learn more!)

Subsets Sums is $$NP-HARD$$, which means there is no known polynomial time solution to this problem. It can be solved by a variety of methods, such as Dynamic Programming. In this case, $$N$$, the number of items is very small ($$N \leq 20$$), so we can actually "enumerate" all possible choices of subset. With a little bit of counting we can prove that, for any $$N$$-element set, there are $$2^N$$ possible subsets. In this case, $$N = 20$$ so $$2^N = 1,048,576$$. There are around a million choices. If we "try" each possible choice (i.e.: by brute force), and see what they add up to (in terms of total amount of each macro-nutrient), then we can see if there is a configuration that works.

To implement this, you can try a recursive function with "Backtracking" or use "Bitmasks".

  1. $$|N|$$ is small, at most $$20$$. This means a brute force (O($$2^N$$)) solution would pass.
  2. With $$N$$ items, there are exactly $$2^N$$ ways to pick a subset of them.
  3. If we were to pick a subset, we can quickly check if it works.
  1. Immediately upon seeing this problem, advanced coders will use the constraints to their advantage. Since $$N$$ is small, even a highly inefficient (exponential) solution would pass. This guided our ideas towards a brute-force solution using "subsets".
  2. Instead of asking "How do we find a set of food that works", we can ask a form of reverse question: "If I have a set of food, can I quickly check that it works?" In this case, the answer is YES. If I know what food I was going to eat, I could check the total amount of protein, carbs, and fat, and check if these are equal to my targets. Because of this fact, it was easy to check every possibility to find our answer.
  • "Keep it Simple Stupid" (KISS) and "Exploit the Constraints". These "catch-phrases" can help minimize your risk of errors, save you time, and increase your chance of getting AC/Accepted on the first try.
  • Brute Force / Exhaustive Search / Subsets and Bitmasks
  • Dynamic Programming / DP / Subset Sums
  • DP / Bitmask DP
  • NP Hard Problems