---
# System prepended metadata

title: 9 dynamic programming

---

# 9 dynamic programming


## The knapsack problem

### The simple solution
![](https://hackmd.io/_uploads/BkaLAYOi3.jpg)

### Dynamic programming

![](https://hackmd.io/_uploads/BJ9GNR_s3.jpg)

ruby code 
```ruby=
require 'terminal-table'

products = {
  stereo: { price: 3000, weight: 4 },
  laptop: { price: 2000, weight: 3 },
  guitar: { price: 1500, weight: 1 },
  iphone: { price: 2000, weight: 1 },
}

bag_sizes = [1, 2, 3, 4]

iterations = {
  initial: {
    1 => { price: 0, items: [] },
    2 => { price: 0, items: [] },
    3 => { price: 0, items: [] },
    4 => { price: 0, items: [] },
  }
}
prev_iteration = iterations[:initial].dup

products.each do |product_name, product|
  current_iteration = {}

  bag_sizes.each_with_index do |pound, index|
    if product[:weight] > pound
      current_iteration[pound] = prev_iteration[pound].dup
    else
      current_iteration[pound] = {
        price: product[:price],
        items: [product_name]
      }

      remaining_pound = pound - product[:weight]
      if remaining_pound > 0
        current_iteration[pound][:price] += prev_iteration[remaining_pound][:price]
        current_iteration[pound][:items] += prev_iteration[remaining_pound][:items]
      end
    end

    if current_iteration[pound][:price] < prev_iteration[pound][:price]
      current_iteration[pound] = prev_iteration[pound].dup
    end
  end

  iterations.merge!(product_name => current_iteration)
  prev_iteration = current_iteration.dup
end

rows = []
iterations.each do |product_name, hsh|
  row_data = hsh.values.map do |result|
    "#{result[:price]} -> #{result[:items]}"
  end
  rows << [product_name, *row_data]
end
table = Terminal::Table.new :headings => ['', '1', '2', '3', '4'], :rows => rows
puts table

```



### What happens if you add an item?
![](https://hackmd.io/_uploads/SJC4N0din.jpg)

![](https://hackmd.io/_uploads/H1Qp4ROs2.jpg)


### exercise

![](https://hackmd.io/_uploads/HyNuVR_i3.jpg)

Answer: No. At every iteration, you’re storing the current max estimate.
The estimate can never get worse than it was before!

### What happens if you change the order of the rows?
![](https://hackmd.io/_uploads/Hyo7SA_j2.jpg)


### What happens if you add a smaller item?
![](https://hackmd.io/_uploads/HkMLH0do3.jpg)


### Can you steal fractions of an item?

![](https://hackmd.io/_uploads/S1DU80_sh.jpg)

### Optimizing your travel itinerary
![](https://hackmd.io/_uploads/Byin-JKsn.jpg)
![](https://hackmd.io/_uploads/SJSpZytj2.jpg)

### Handling items that depend on each other
![](https://hackmd.io/_uploads/S19ufyFj3.jpg)



## Longest common substring

![](https://hackmd.io/_uploads/SJmENJFs2.jpg)

### Feynman algorithm
1. Write down the problem.
2. Think real hard.
3. Write down the solution.

### The solution

![](https://hackmd.io/_uploads/HktfaJFsn.jpg)

![](https://hackmd.io/_uploads/ByHE6JKjh.jpg)


### Longest common subsequence
![](https://hackmd.io/_uploads/BJrtT1ti3.jpg)

### Longest common subsequence—solution
![](https://hackmd.io/_uploads/Hktqpktsn.jpg)



