Happy Monday!
I will be taking on a problem called 'Cake Thief'... sounds fun!
It is just a rehash of the classic puzzle called "the unbounded knapsack problem."
It is solved by using a bottom up programming method. This is an almost improved version of a greedy algo. You fill up an array with previous solutions and then work out the next in the sequence depending on the previous ones.
In this example, you calculate for all the weights up to the one you need. To determine the next max value you loop through all possible weights adding where they would fit (i.e. looking backwards in the array).
Top comments (0)