We provide efficient Python solutions to the Dropbox challenges.
Q3.py - The Dropbox Diet
We solve the Dropbox Diet challenge with dynamic programming.
The key step is to recognise the problem as an instance of subset-sum, and use the straightforward pseudo-polynomial time dynamic programming algorithm, which runs in time O(n(P-N)), where n is the number of activities, P is the sum of the calorific values of the activities with positive calorific value, and N is the sum of the calorific values of the activities with negative calorific value.
We use this algorithm to determine the existence of a solution, which is then solution is then found by backtracking.
To run the code, simply pass in a formatted text file containing the problem specification to
cat knapsack.txt | python Q3.py
coding-six-hours mexican-coke cookies