// LLP-IncrKnapsack: add a single item (w, v) on top of previous row C.

fn llp_incr_knapsack(w: usize, v: i32, c: &[i32]) -> Vec<i32> {
    let n = c.len();
    let mut g = vec![0i32; n];
    let mut changed = true;
    while changed {
        changed = false;
        for ci in 0..n {
            let skip = c[ci];
            let take = if ci >= w { c[ci - w] + v } else { -1 };
            let best = skip.max(take);
            if g[ci] < best { g[ci] = best; changed = true; }
        }
    }
    g
}

fn main() {
    let c = vec![0, 0, 3, 3, 3, 3, 3, 3, 3];
    let g = llp_incr_knapsack(3, 4, &c);
    println!("new row G = {:?}", g);
}