1. 编写一个简单的程序,解决0-1背包问题。设N=5,C=10,w={2,2,6,5,4},v={6,3,5,4,6},C++语言
时间: 2024-12-21 13:27:14 浏览: 4
0-1背包问题是一个经典的动态规划问题,目标是在给定容量C和物品重量w以及价值v的情况下,选择能装入背包的最大价值物品组合。下面是一个简化的C++程序示例,用于解决这个问题:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int knapSack(int W, vector<int>& wt, vector<int>& val, int n) {
vector<vector<int>> dp(n + 1, vector<int>(W + 1));
// 构建动态规划表
for (int i = 1; i <= n; ++i) {
for (int w = 1; w <= W; ++w) {
if (wt[i - 1] <= w) {
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][W];
}
int main() {
int N = 5;
int C = 10;
vector<int> w = {2, 2, 6, 5, 4};
vector<int> v = {6, 3, 5, 4, 6};
cout << "最大价值: " << knapSack(C, w, v, N) << endl;
return 0;
}
```
在这个程序中,`knapSack`函数采用二维动态规划数组`dp`来存储每种情况下的最优解。它通过比较包含当前物品和不包含当前物品两种情况下的最大价值,最终找到整个背包的最大价值。
阅读全文