请用动态规划法编程实现0-1背包问题。
时间: 2023-06-03 10:07:21 浏览: 123
好的,以下是0-1背包问题的动态规划代码:
```
#include <iostream>
#include <vector>
using namespace std;
int zeroOneKnapsack(vector<int>& weights, vector<int>& values, int maxWeight) {
int n = weights.size();
vector<vector<int>> dp(n + 1, vector<int>(maxWeight + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= maxWeight; j++) {
if (weights[i - 1] <= j) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][maxWeight];
}
int main() {
vector<int> weights = {1, 3, 4, 5};
vector<int> values = {1, 4, 5, 7};
int maxWeight = 7;
int result = zeroOneKnapsack(weights, values, maxWeight);
cout << result << endl;
return 0;
}
```
这段代码实现了动态规划的解法,解决了0-1背包问题。
阅读全文