DS Notes

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

#![allow(unused)]
fn main() {
// 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 \{\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\\ ⋮& ⋮\\ p_k+\text{maxRevenue}(L-l_k)& \leftarrow \text{Choosing Option k: yields revenue}{p}_k\text{and cuts off}{l}_k\end{array}$$

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.

#![allow(unused)]
fn main() {
// 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}\le W_{\circ }$

Value: $\{\begin{array}{l}\sum V_{ij}ifn<10\\ \sum V_{ij}ifn\ge 10\end{array}$

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.