Pages

Other Dynamic Programming problems

Sixth and last week of the edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego, again on Dynamic Programming. Just three problems, fully described in this pdf.

The first one, named "Maximum Amount of Gold", states that you have a bag of given capacity, and you see n gold bars of (possibly) different weights. Push as much gold as you can in the bag.

It is easy to say that it is a variation on the classic 0/1 knapsack problem. Here the bars have all the same unitary value, so we just need to know their weight to build our solution. Not much sweat to solve it, anyway I pushed to GitHub first a python script to solve the generic problem, then one tailored on the specific requirements of the problem.

Much more challenging the other two problems. "Partitioning Souvenirs" is a 3-Partition problem. Before solving it, I practiced with the more common 2-partition version. "Maximizing the Value of an Arithmetic Expression" is well described, step by step, in the course, and I guess that I solved it easily only because of this intensive training. You could see my python implementation on GitHub.

No comments:

Post a Comment