knaptime/threshold/
dp.rs

1use crate::types::Item;
2use std::cmp::max;
3
4pub fn knapsack(capacity: u8, items: &[Item<u8, u64>]) -> Result<(u64, usize), String> {
5  // Sort items by weight
6  let mut items = items.to_vec();
7  items.sort_by(|a, b| a.weight.cmp(&b.weight));
8
9  let max_overflow = items
10    .first()
11    .unwrap_or(&Item {
12      weight: 0,
13      value: 0,
14    })
15    .weight as usize;
16
17  let capacity = capacity as usize;
18  let mut dp = vec![0; capacity + max_overflow + 1];
19  let mut weight = vec![0; capacity + max_overflow + 1];
20
21  // Throw error if smallest weight is 0
22  if let Some(item) = items.first() {
23    if item.weight == 0 {
24      return Err("Item weight cannot be 0".to_string());
25    }
26  }
27
28  for i in 0..=(capacity + max_overflow) {
29    for item in &items {
30      if item.weight as usize > i {
31        // Skip to next capacity/set of items once the remaining items won't fit.
32        break;
33      } else {
34        // This items fits
35        // Only consider this if it's fully utilizing the knapsack
36        if i - item.weight as usize == 0 || weight[i - item.weight as usize] != 0 {
37          match item.value.checked_add(dp[i - item.weight as usize]) {
38            Some(use_item_value) => {
39              // Max of (Don't use item) (Use item)
40              dp[i] = max(dp[i], use_item_value);
41              weight[i] = max(
42                weight[i],
43                weight[i - item.weight as usize] + item.weight as usize,
44              )
45            }
46            None => {
47              return Err("Value overflow".to_string());
48            }
49          };
50        }
51      }
52    }
53    if i >= capacity && weight[i] >= capacity {
54      return Ok((dp[i], i));
55    }
56  }
57
58  if items.is_empty() {
59    return Ok((0, 0));
60  }
61
62  Err("Unable to reach threshold".to_string())
63}
knaptime/threshold/dp.rs

knaptime/threshold/
dp.rs
