74 lines
2.9 KiB
Plaintext
74 lines
2.9 KiB
Plaintext
use std::cmp;
|
|
|
|
struct Item {
|
|
name: &'static str,
|
|
weight: usize,
|
|
value: usize
|
|
}
|
|
|
|
fn knapsack01_dyn(items: &[Item], max_weight: usize) -> Vec<&Item> {
|
|
let mut best_value = vec![vec![0; max_weight + 1]; items.len() + 1];
|
|
for (i, it) in items.iter().enumerate() {
|
|
for w in 1 .. max_weight + 1 {
|
|
best_value[i + 1][w] =
|
|
if it.weight > w {
|
|
best_value[i][w]
|
|
} else {
|
|
cmp::max(best_value[i][w], best_value[i][w - it.weight] + it.value)
|
|
}
|
|
}
|
|
}
|
|
|
|
let mut result = Vec::with_capacity(items.len());
|
|
let mut left_weight = max_weight;
|
|
|
|
for (i, it) in items.iter().enumerate().rev() {
|
|
if best_value[i + 1][left_weight] != best_value[i][left_weight] {
|
|
result.push(it);
|
|
left_weight -= it.weight;
|
|
}
|
|
}
|
|
|
|
result
|
|
}
|
|
|
|
|
|
fn main () {
|
|
const MAX_WEIGHT: usize = 400;
|
|
|
|
const ITEMS: &[Item] = &[
|
|
Item { name: "map", weight: 9, value: 150 },
|
|
Item { name: "compass", weight: 13, value: 35 },
|
|
Item { name: "water", weight: 153, value: 200 },
|
|
Item { name: "sandwich", weight: 50, value: 160 },
|
|
Item { name: "glucose", weight: 15, value: 60 },
|
|
Item { name: "tin", weight: 68, value: 45 },
|
|
Item { name: "banana", weight: 27, value: 60 },
|
|
Item { name: "apple", weight: 39, value: 40 },
|
|
Item { name: "cheese", weight: 23, value: 30 },
|
|
Item { name: "beer", weight: 52, value: 10 },
|
|
Item { name: "suntancream", weight: 11, value: 70 },
|
|
Item { name: "camera", weight: 32, value: 30 },
|
|
Item { name: "T-shirt", weight: 24, value: 15 },
|
|
Item { name: "trousers", weight: 48, value: 10 },
|
|
Item { name: "umbrella", weight: 73, value: 40 },
|
|
Item { name: "waterproof trousers", weight: 42, value: 70 },
|
|
Item { name: "waterproof overclothes", weight: 43, value: 75 },
|
|
Item { name: "note-case", weight: 22, value: 80 },
|
|
Item { name: "sunglasses", weight: 7, value: 20 },
|
|
Item { name: "towel", weight: 18, value: 12 },
|
|
Item { name: "socks", weight: 4, value: 50 },
|
|
Item { name: "book", weight: 30, value: 10 }
|
|
];
|
|
|
|
let items = knapsack01_dyn(ITEMS, MAX_WEIGHT);
|
|
|
|
// We reverse the order because we solved the problem backward.
|
|
for it in items.iter().rev() {
|
|
println!("{}", it.name);
|
|
}
|
|
|
|
println!("Total weight: {}", items.iter().map(|w| w.weight).sum::<usize>());
|
|
println!("Total value: {}", items.iter().map(|w| w.value).sum::<usize>());
|
|
}
|