用c++递归和迭代两种方法写出0-1背包问题
时间: 2023-12-02 20:05:02 浏览: 27
递归实现:
```
int knapsack(int weight[], int value[], int n, int W) {
if (n == 0 || W == 0)
return 0;
if (weight[n - 1] > W)
return knapsack(weight, value, n - 1, W);
int include = knapsack(weight, value, n - 1, W - weight[n - 1]) + value[n - 1];
int exclude = knapsack(weight, value, n - 1, W);
return max(include, exclude);
}
```
迭代实现:
```
int knapsack(int weight[], int value[], int n, int W) {
int dp[n + 1][W + 1];
for (int i = 0; i <= n; ++i) {
for (int w = 0; w <= W; ++w) {
if (i == 0 || w == 0)
dp[i][w] = 0;
else if (weight[i - 1] <= w)
dp[i][w] = max(value[i - 1] + dp[i - 1][w - weight[i - 1]], dp[i - 1][w]);
else
dp[i][w] = dp[i - 1][w];
}
}
return dp[n][W];
}
```