请你用C++写一个01背包问题
时间: 2024-05-10 17:17:56 浏览: 13
好的,以下是用 C++ 写的 01 背包问题代码:
```c++
#include <iostream>
using namespace std;
int main()
{
int n, W;
cin >> n >> W; // 输入物品数量和背包容量
int wt[n], val[n];
for (int i = 0; i < n; i++) {
cin >> wt[i] >> val[i]; // 输入每个物品的重量和价值
}
int dp[n + 1][W + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0) {
dp[i][w] = 0; // 初始化第一行和第一列为0
} else if (wt[i - 1] <= w) {
dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]); // 转移方程
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
cout << dp[n][W] << endl; // 输出最大价值
return 0;
}
```
以上代码实现了一个基本的 01 背包问题,时间复杂度为 O(nW),其中 n 是物品数量,W 是背包容量。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)