[The Beauty of Programming] Dynamic Programming – Discount and Backpack

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
this is a simplified version from the book…

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.

- 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.

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

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>