01背包问题动态规划javascript代码和运行结果
时间: 2023-10-31 12:02:31 浏览: 44
好的,以下是01背包问题的动态规划JavaScript代码和运行结果:
```javascript
function knapsack(capacity, weights, values) {
const n = values.length;
let dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= capacity; j++) {
if (weights[i - 1] <= j) {
dp[i][j] = Math.max(
dp[i - 1][j],
dp[i - 1][j - weights[i - 1]] + values[i - 1]
);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][capacity];
}
const capacity = 50;
const weights = [10, 20, 30];
const values = [60, 100, 120];
console.log(knapsack(capacity, weights, values)); // 220
```
运行结果:
```
220
```
解释:
- `capacity`:背包最大容量为50
- `weights`:物品的重量分别为10、20、30
- `values`:物品的价值分别为60、100、120
- `console.log(knapsack(capacity, weights, values));`:调用 `knapsack` 函数,输出结果 `220`,即最大价值为220。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)