Skip to content

Instantly share code, notes, and snippets.

@likr
Created July 15, 2013 23:52
Show Gist options
  • Save likr/6004578 to your computer and use it in GitHub Desktop.
Save likr/6004578 to your computer and use it in GitHub Desktop.
Rust code for solving knapsack problem.
fn dp (p : &[int], w : &[int], c : int) -> int {
let mut z = std::vec::from_elem((c + 1) as uint, 0);
for p.iter().zip(w.iter()).advance |(pj, wj)| {
for std::uint::range_rev(c as uint, (*wj - 1) as uint) |k| {
z[k] = match z[k - *wj as uint] + *pj {
v if v > z[k] => v,
_ => z[k]
}
}
}
return z[c];
}
fn main() {
let p = [6, 5, 8, 9, 6, 7, 3];
let w = [2, 3, 6, 7, 5, 9, 4];
let c = 9;
let opt = 15;
let obj = dp(p, w, c);
assert!(opt == obj);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment