knapsack.rs

#![feature(inclusive_range_syntax)]

extern crate fnv;

use fnv::FnvHashMap;
use std::cmp::min;


type Item = (usize, usize, usize);
type Opt = (usize, usize);


pub fn best(W: usize, items: &[Item]) -> (usize, Vec<usize>) {
    let n = items.len();
    if n == 0 {
        return (0, vec![]);
    }
    let mut cache = vec![FnvHashMap::default(); n];

    fn opt(items: &[Item],
           cache: &mut[FnvHashMap<usize, Opt>],
           i:     usize,
           x:     usize) -> Opt {
        if x == 0 {
            return (0, 0);
        }

        if let Some(&cached_opt) = cache[i].get(&x) {
            return cached_opt;
        }

        let (w, v, c) = items[i];

        let mut max_val = 0;
        let mut max_j   = 0;
        for j in 0..=min(c, x / w) {
            let (mut opt_val, _) =
                if let (Some(i_), Some(x_)) = (i.checked_sub(1),
                                               x.checked_sub(j * w)) {
                    opt(items, cache, i_, x_)
                } else {
                    (0, 0)
                };
            opt_val += j * v;

            if opt_val > max_val {
                max_val = opt_val;
                max_j = j;
            }
        }

        cache[i].insert(x, (max_val, max_j));
        (max_val, max_j)
    }

    let (opt_val, opt_j) = opt(items, &mut cache, n - 1, W);

    let mut opt_items = vec![0; n];
    opt_items[n - 1] = opt_j;
    let mut x = W - items[n - 1].0 * opt_j;
    for i in (0..n - 1).rev() {
        if let Some(&(_, cache_j)) = cache[i].get(&x) {
            opt_items[i] = cache_j;
            x -= items[i].0 * cache_j;
        }
    }

    (opt_val, opt_items)
}