0-1 Knapsack problem - implementation

1. Check out Rustfmt.

2. There's a Clippy warning for zero_one_knapsack: explicit lifetimes given in parameter types where they could be elided.

3. Don't prefix every parameter with p. There's no naming conflict and it adds confusion to everyone that tries to use the API. Especially for variables like padded_weight, where "padded" is another English word!

4. Introduce a key method to DRY up Ord / PartialEq / Hash implementations.

5. A leading _ means that item is unused but must be present for some reason; don't call your methods that. Switch to words since identifiers can't start with numbers

6. Start iteration in zero_one_knapsack_items at 0. This simplifies the logic and shows that take_while can be removed.

7. This also leads to using iter and enumerate instead of operating on a range.

8. In turn, this leads to removing the need for indexing into items.

9. Remove the result temporary variable. It doesn't introduce a useful name and doesn't need to occur in a different temporal location.

10. There is a filter_map that does two operations in one, but I like the separation of filter and map here. You almost want a scan_map.

11. There's no need to specify type on collect; it's inferred from the return type of the function.

12. I'm not a fan of the truncated variable names. Computers don't care about long names, but humans do care about short names. This is especially true when there are overlapping meanings for prefixes like inc (included or inclusive).

13. Prefer iterating on a slice instead of on a range of numbers. If you need the number, use enumerate; this avoids out-of-bounds checking on each index operation.

14. Implement Default for your type if there's an appropriate value.

15. Import Ord and max to make that code a bit cleaner to read.

use std::cmp::{Ord, max};

#[derive(Debug, Clone)]
struct Item {
    value: usize,
    weight: usize,
}

impl Item {
    fn new(value: usize, weight: usize) -> Item {
        Item {
            value: value,
            weight: weight,
        }
    }
}

#[derive(Debug, Clone)]
struct Info {
    ks_value: usize,
    added_weight: usize,
    included: bool,
}

impl Info {
    fn new(ks_value: usize, added_weight: usize, included: bool) -> Info {
        Info {
            ks_value: ks_value,
            added_weight: added_weight,
            included: included,
        }
    }

    fn key(&self) -> usize {
        self.ks_value
    }
}

impl Ord for Info {
    fn cmp(&self, other: &Info) -> std::cmp::Ordering {
        self.key().cmp(&other.key())
    }
}

impl PartialOrd for Info {
    fn partial_cmp(&self, other: &Info) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl PartialEq for Info {
    fn eq(&self, other: &Info) -> bool {
        self.key() == other.key()
    }
}

impl Eq for Info {}

impl Default for Info {
    fn default() -> Info {
        Info::new(0, 0, false)
    }
}

fn zero_one_knapsack_items<'a>(items: &'a [Item],
                               max_weight: usize,
                               subproblems: &[Vec<Info>]) -> Vec<&'a Item>
{
    items.iter().enumerate()
        .rev()
        .scan(max_weight, |w, (i, item)| {
            let subproblem = &subproblems[i+1][*w];
            *w -= subproblem.added_weight;
            Some((item, subproblem.included))
        })
        .filter(|&(_, included)| included)
        .map(|(item, _)| item)
        .collect()
}

fn zero_one_knapsack(items: &[Item], max_weight: usize) -> Vec<&Item> {
    let mut subproblems = vec![vec![Info::default(); max_weight + 1]; items.len() + 1];

    for (i, item) in items.iter().enumerate() {
        for w in 0..max_weight + 1 {
            let w_i = item.weight;
            let exclusive_cost = subproblems[i][w].ks_value;
            subproblems[i + 1][w] = if w < w_i {
                Info::new(exclusive_cost, 0, false)
            } else {
                let inclusive_cost = subproblems[i][w - w_i].ks_value + item.value;
                max(Info::new(exclusive_cost, 0, false),
                    Info::new(inclusive_cost, w_i, true))
            }
        }
    }

    zero_one_knapsack_items(items, max_weight, &subproblems)
}

fn main() {
    let items = [Item::new(92, 23),  // 1
                 Item::new(57, 31),  // 1
                 Item::new(49, 29),  // 1
                 Item::new(68, 44),  // 1
                 Item::new(60, 53),  // 0
                 Item::new(43, 38),  // 1
                 Item::new(67, 63),  // 0
                 Item::new(84, 85),  // 0
                 Item::new(87, 89),  // 0
                 Item::new(72, 82)]; // 0

    for i in zero_one_knapsack(&items, 165) {
        println!("{:?}", i);
    }
}