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

)