写一份动态规划解决部分背包问题的c++代码
时间: 2023-08-02 10:31:33 浏览: 56
好的,以下是动态规划解决部分背包问题的 C++ 代码,具体注释请查看代码中的注释:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 物品数量和背包容量
int n, W;
cin >> n >> W;
// 每个物品的重量和价值
vector<int> wt(n), val(n);
for (int i = 0; i < n; i++) {
cin >> wt[i] >> val[i];
}
// 初始化动态规划表
vector<int> dp(W + 1);
// 填充动态规划表
for (int i = 0; i < n; i++) {
for (int j = W; j >= wt[i]; j--) {
// 取当前物品和不取当前物品中价值更大的一种情况
dp[j] = max(dp[j], dp[j - wt[i]] + val[i]);
}
}
// 输出最终结果
cout << dp[W] << endl;
return 0;
}
```
注意:这份代码是解决“部分背包问题”的,即每个物品可以选择放入一部分,而不一定完全放入。如果要解决“0/1背包问题”,只需要将第11行修改为 `vector<int> dp(W + 1, 0);`,第14行修改为 `for (int j = W; j >= wt[i]; j--)` 即可。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)