给我一段尽量简洁的c++代码,解决一个01背包问题
时间: 2024-10-20 14:13:19 浏览: 20
以下是一个简单的C++代码片段,使用了动态规划方法来解决01背包问题:
```cpp
#include <iostream>
#include <vector>
int knapSack(int W, std::vector<int>& wt, std::vector<int>& val, int n) {
std::vector<int> dp(n + 1, 0); // 初始化一个大小为n+1的数组,dp[i]表示前i个物品能够达到的最大价值
for (int i = 1; i <= n; ++i) { // 遍历所有物品
for (int w = W; w >= wt[i]; --w) { // 从当前物品的最大重量到0
if (val[i] > dp[w - wt[i]]) { // 如果包含当前物品比不包含更有价值
dp[w] = dp[w - wt[i]] + val[i];
}
}
}
return dp[W]; // 返回背包容量W下的最大价值
}
int main() {
int W = 50;
std::vector<int> wt = {10, 20, 30}; // 物品重量
std::vector<int> val = {60, 100, 120}; // 物品价值
int n = wt.size();
std::cout << "Max value in a knapsack of capacity " << W << ": " << knapSack(W, wt, val, n) << "\n";
return 0;
}
```
这段代码定义了一个名为`knapSack`的函数,接受背包的容量、物品的重量和价值向量以及物品数量作为输入,计算并返回背包最大价值。
阅读全文