For a while I’ve been reading programming pearls…Then I wanted some change so picked up the beauty of programming (again). This time it went pretty smooth, due to the fact that’s the second time I read it – although the first time I didn’t really look into all the details…Anyway I want to blog about two dynamic programming problems:

Problem: Discount
Note:
this is a simplified version from the book…

Problem:
suppose you need to buy N books. The price is $p / book, and if you order several books together in an order you will get corresponding discount as following:
1 book – d1
2 books – d2
3 books – d3
4 books – d4
5 books – d5
Please compute the minimum money you have to spend.

Solution:
- Let f(n) to be the minimum money to buy n books.
- f(n) = min(
f(n-1) + p*d1,
f(n-2) + 2*p*d2,
f(n-3) + 3*p*d3,
f(n-4) + 4*p*d4,
f(n-5) + 5*p*d5
)
- The initial values (or the termination conditions if you see it as recursive…) are first 5 items.

Problem: Backpack
The official name should be ’0-1 knacksack problem’ if I googled it correctly…The problem is suppose you have a bag that can afford weight w, and you got n items that values are v[i] and weight are w[i], calculate the maximum value you can put in your bag.

Solution:
The key here is to identify the variables for dynamic programming. So if we look at this problem as f(n, w) where n means n items and w means the weight capacity is w, then the model is obvious:
f(n, w) = max(
f(n-1, w), // if we don’t put the nth item in the bag
f(n-1, w – w[n-1]) + v[n-1] // if we put the nth item in the bag
)