请给出c++的完全背包问题的优化代码
时间: 2023-07-24 09:01:12 浏览: 102
以下是使用动态规划的C++代码来解决完全背包问题的优化版本:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int knapsack(int W, vector<int>& wt, vector<int>& val) {
int n = wt.size();
vector<int> dp(W + 1, 0);
for (int i = 0; i < n; i++) {
for (int j = wt[i]; j <= W; j++) {
dp[j] = max(dp[j], dp[j - wt[i]] + val[i]);
}
}
return dp[W];
}
int main() {
int W = 10; // 背包的容量
vector<int> wt = {2, 3, 4, 5}; // 物品的重量
vector<int> val = {3, 4, 5, 6}; // 物品的价值
int maxVal = knapsack(W, wt, val);
cout << "背包能装的最大价值为: " << maxVal << endl;
return 0;
}
```
在优化版本的代码中,我们使用一维数组`dp`来保存当前背包容量下的最大价值。通过遍历物品和背包容量,我们可以更新`dp`数组中的值。最后,返回`dp[W]`即为背包能够装载的最大价值。
注意:以上代码仅实现了完全背包问题的优化解法,假设物品的重量和价值都为正整数。如果存在其他约束条件,请根据实际情况进行修改。
阅读全文