C++算法编写穷举法算法求解背包0/1问题
时间: 2024-11-15 08:23:14 浏览: 53
cpp代码-分支限界法求解0-1背包问题
在C++中,我们可以使用穷举法(也称为暴力搜索法或枚举法)来解决背包0/1问题,这是一个经典的动态规划问题。这个问题通常涉及到给定一组物品,每个物品有自己的价值和重量,以及一个最大容量的背包,目标是在不超过背包容量的情况下,选择物品使得总价值最大化。
下面是一个简单的穷举法算法步骤:
1. 定义两个数组:`value[i]`表示第`i`个物品的价值,`weight[i]`表示其重量。
2. 创建一个二维数组`dp`,其中`dp[i][w]`表示前`i`个物品能装入容量为`w`的最大价值。
3. 对于每个物品`i`和每个可能的背包容量`w`,从`0`到`capacity`循环:
- 如果背包还有空间(即`weight[i] <= w`),则计算当前物品加入后的最大价值:`dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])`。
- 否则,如果物品放不下,则直接复制上一个物品的值:`dp[i][w] = dp[i-1][w]`。
4. 最终,`dp[n][capacity]`就是所求的答案,其中`n`是物品的数量。
```cpp
#include <iostream>
using namespace std;
int knapSack(int capacity, int weight[], int value[], int n) {
int dp[n+1][capacity+1];
for (int i = 0; i <= n; ++i)
for (int w = 0; w <= capacity; ++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][capacity];
}
int main() {
int capacity = 50, weight[] = {10, 20, 30}, value[] = {60, 100, 120}, n = sizeof(weight)/sizeof(weight[0]);
cout << "Max value in the knapsack is: " << knapSack(capacity, weight, value, n);
return 0;
}
```
阅读全文