2
\$\begingroup\$

Given a set of items with a weight and a value, this problem gives the subset of items which maximize value so that their combined weights is less or equal than a given maximum weight. This solution runs in \$O(w\cdot n)\$ where \$n\$ is the number of items and \$w\$ is the max weight.

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

impl Item {

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

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

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

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

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.ks_value == other.ks_value
    }
}

impl Eq for Info {}

fn _0_1_knapsack_items<'a>(items: &'a[Item], max_weight: usize, subproblems: &[Vec<Info>]) -> Vec<&'a Item>{
        (1..items.len() + 1).rev()
        .scan(max_weight, |w, i| {
                let sub    = &subproblems[i][*w];
                let result = (i, sub.included);
                *w -= sub.added_weight;
                Some(result)
        })
        .filter(|&(_, inc)| inc)
        .take_while(|&(i, _)| i > 0)
        .map(|(i, _)| &items[i - 1])
        .collect::<Vec<&Item>>()
}

fn _0_1_knapsack<'a>(items: &'a [Item], max_weight: usize) -> Vec<&'a Item>{
    let mut subproblems = vec! [ vec! [ Info::new(0, 0, false);
                                       max_weight + 1 ]; 
                                 items.len() + 1 ];
    for i in 0..items.len() {
        for w in 0..max_weight + 1 { 
            let w_i      = items[i].weight;
            let exc_cost = subproblems[i][w].ks_value;
            subproblems[i + 1][w] = if  w < w_i {
                Info::new(exc_cost, 0, false)
            } 
            else {
                let inc_cost = subproblems[i][w - w_i].ks_value 
                               + items[i].value;
                std::cmp::max(Info::new(exc_cost, 0, false), 
                              Info::new(inc_cost, w_i, true))     
            }
        }
    }
    _0_1_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 _0_1_knapsack(&items, 165){
        println!("{:?}", i);
    }
}
\$\endgroup\$
1
\$\begingroup\$
  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);
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I feel like there should be a more iterator-focused version of zero_one_knapsack, but I'm not seeing it right now. \$\endgroup\$ – Shepmaster Oct 17 '16 at 2:16
  • \$\begingroup\$ take_while wasn't needed in my version either, I probably change something and forgot to remove it, same with result local variable * facepalm *. As always that was a great review, thanks :). \$\endgroup\$ – MAG Oct 17 '16 at 2:48
  • 1
    \$\begingroup\$ @MAG oh, it's definitely not needed in the original version. I didn't change any external behavior (I hope). My point is that by rewriting the code as i + 1 > 0 made it very obvious that it would always be true, seeing as how it was a usize. \$\endgroup\$ – Shepmaster Oct 17 '16 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.