用rust写一个背包问题
时间: 2023-07-07 12:18:29 浏览: 109
好的,以下是一个用 Rust 实现的背包问题的代码示例:
```rust
fn knapsack(capacity: usize, weights: &[usize], values: &[usize]) -> usize {
let n = weights.len();
let mut dp = vec![vec![0; capacity + 1]; n + 1];
for i in 1..=n {
for j in 1..=capacity {
if weights[i - 1] > j {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = std::cmp::max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
}
}
}
dp[n][capacity]
}
fn main() {
let capacity = 10;
let weights = vec![2, 3, 4, 5];
let values = vec![3, 4, 5, 6];
let result = knapsack(capacity, &weights, &values);
println!("Maximum value: {}", result);
}
```
这个代码会计算一个背包最大可以装多少价值的物品,其中 `capacity` 是背包的容量,`weights` 是物品的重量,`values` 是物品的价值。其中使用动态规划的思想来解决背包问题。