01背包问题回溯法c语言
时间: 2023-10-06 18:14:05 浏览: 45
下面是01背包问题的回溯法c语言代码:
```
#include <stdio.h>
#define MAX_N 100
int n, W;
int w[MAX_N], v[MAX_N];
int max_value = 0;
int cur_weight = 0, cur_value = 0;
void dfs(int cur)
{
if (cur == n) {
if (cur_value > max_value) {
max_value = cur_value;
}
return;
}
if (cur_weight + w[cur] <= W) {
cur_weight += w[cur];
cur_value += v[cur];
dfs(cur + 1);
cur_weight -= w[cur];
cur_value -= v[cur];
}
dfs(cur + 1);
}
int main()
{
scanf("%d%d", &n, &W);
for (int i = 0; i < n; i++) {
scanf("%d%d", &w[i], &v[i]);
}
dfs(0);
printf("%d\n", max_value);
return 0;
}
```
解释:
- MAX_N:定义物品的最大数量;
- n:物品的数量;
- W:背包的容量;
- w[MAX_N]、v[MAX_N]:分别存储物品的重量和价值;
- max_value:当前最大价值;
- cur_weight、cur_value:当前背包重量和价值;
- dfs():深度优先搜索函数;
- cur:当前处理的物品序号。
在dfs()函数中,首先判断是否处理完所有物品,如果是,就更新最大价值max_value,并返回;否则,分两种情况考虑:
- 如果把当前物品放入背包中,且背包容量还够,就更新当前背包重量和价值,并继续处理下一个物品;
- 如果不把当前物品放入背包中,就直接处理下一个物品。
最后,在main()函数中,读入物品数量n和背包容量W,以及每个物品的重量和价值,然后调用dfs()函数进行搜索,并输出最大价值max_value。
注:此代码为原创,如需转载请注明出处。