# 9 dynamic programming

## The knapsack problem

### The simple solution

### Dynamic programming


ruby code

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?


### exercise


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?

### What happens if you add a smaller item?

### Can you steal fractions of an item?


### Optimizing your travel itinerary

### Handling items that depend on each other

## Longest common substring


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

### The solution



### Longest common subsequence

### Longest common subsequence—solution