CSCA 5414: Greedy Algorithms

Rod cutting is shown as a canonical example of using DP in a recursive and then memoized setting (a third example recovering the data from the table is elided for brevity).

// Naive attempt to implement the recurrence (see dp_rodcutting.ipynb)
fn max_revenue_recursive(len: i32, sizes: &Vec<i32>, prices: &Vec<f64>) -> i32 {
  if len == 0 {
    return 0;
  }
  if len < 0 {
    return -100_000_000;
  }
  let k = sizes.len();
  assert_eq!(prices.len(), k);
  let mut option_values = vec![];
  for i in 0..k {
    option_values.push(prices[i] + max_revenue_recursive(
      len-sizes[i], sizes, prices
    ) as f64);
  }
  option_values.push(0.);
  option_values.into_iter().reduce(f64::max).unwrap() as i32
}

#[test]
fn examples() {
    let sizes = vec![1, 3, 5, 10, 30, 50, 75];
    let prices = vec![0.1, 0.2, 0.4, 0.9, 3.1, 5.1, 8.2];
    assert_eq!(3.0, max_revenue_recursive(30, &sizes, &prices).round());
    assert_eq!(5.0, max_revenue_recursive(50, &sizes, &prices).round());
    assert_eq!(33.0, max_revenue_recursive(300, &sizes, &prices).round());
}

Assumptions

• $k \ge 1$
• L is a positive usize
• sizes and prices will always have the same length

Fining an optimal substructure

Given some length $L$, we say

1. A cut of $L_i$ pays $P_i$ revenue.
2. Optimally cut remaining $L-L_i$

Example recurrence relations

$$\text{maxRevenue}(L) = \max \left\{ \begin{array}{ll} 0 & \leftarrow \text{Waste the current length of rod without cutting it} \\ p_1 + \text{maxRevenue}(L-l_1) & \leftarrow \text{Choosing Option 1: yields revenue } p_1 \text{ and cuts off } l_1 \\ p_2 + \text{maxRevenue}(L-l_2) & \leftarrow \text{Choosing Option 2: yields revenue } p_2 \text{ and cuts off } l_2 \\ \vdots & \vdots \\ p_k + \text{maxRevenue}(L-l_k) & \leftarrow \text{Choosing Option k: yields revenue } p_k \text{ and cuts off } l_k \end{array}\right.$$

Example base cases

• $\text{maxRevenue}(L) = 0$ whenever $L= 0$. If no rod to cut then nothing to do.
• $\text{maxRevenue}(L) = - \infty$ whenever $L < 0$. If there is negative rod to cut, we will “punish” the cutter infinitely.

// Memoized version
fn max_revenue_memoize(len: i32, sizes: &Vec<i32>, prices: &Vec<f64>) -> f64 {
    let n = len as usize;
    let k = sizes.len();
    assert_eq!(prices.len(), k);

    let mut table = vec![0.; n + 1];
    let mut vals = vec![];

    for i in 1..n + 1 {
        for j in 0..k {
            let i = i as i32;
            if i - sizes[j] >= 0 {
                let idx = (i - sizes[j]) as usize;
                vals.push(prices[j] + table[idx] as f64);
                vals.push(0.);
                table[i as usize] = vals
                  .clone()
                  .into_iter()
                  .reduce(f64::max)
                  .unwrap()
            }
        }
    }
    table[n]
}

#[test]
fn examples() {
    let sizes = vec![1, 3, 5, 10, 30, 50, 75];
    let prices = vec![0.1, 0.2, 0.4, 0.9, 3.1, 5.1, 8.2];
    assert_eq!(3.0, max_revenue_memoize(30, &sizes, &prices).round());
    assert_eq!(5.0, max_revenue_memoize(50, &sizes, &prices).round());
    assert_eq!(33.0, max_revenue_memoize(300, &sizes, &prices).round());
}

When no optimal substructure exists

Noting some conditions of the well-known knapsack problem, where $W$ is weight.

$\sum W_{ij} \leq W_{\circ}$

Value: $\begin{cases} \sum V_{ij}\ if\ n\ \lt 10 \\ \sum V_{ij}\ if\ n\ \ge 10 \\ \end{cases}$

An alternate example of non-optimal substructure is path-finding, where movement decisions may be disjoint. The sequencing of finding optimal substructures thus becomes the driving factor.