分支限界法 01背包c语言,算法笔记分支限界法01背包问题 输出最优值和最优解 代码要有注释
时间: 2024-01-17 16:05:46 浏览: 90
分支限界算法 01背包问题
4星 · 用户满意度95%
好的,下面是使用分支限界法解决01背包问题的C语言代码,包含注释:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100 // 物品数量的最大值
#define MAX_W 1000 // 背包容量的最大值
int n, W; // 物品数量、背包容量
int w[MAX_N], v[MAX_N]; // 物品的重量、价值
int max_v = 0, max_x[MAX_N]; // 最优解的价值、每个物品选择的情况
// 计算上界,以价值为下界,剩余物品按单位价值从大到小装满背包
double upper_bound(int i, int cur_w, int cur_v) {
double bound = cur_v;
int j;
for (j = i; j < n && cur_w + w[j] <= W; j++) {
bound += v[j];
cur_w += w[j];
}
if (j < n) {
bound += (W - cur_w) * 1.0 * v[j] / w[j];
}
return bound;
}
// 搜索函数
void dfs(int i, int cur_w, int cur_v, int x[]) {
if (i == n) { // 到达叶子节点,更新最优解
if (cur_v > max_v) {
max_v = cur_v;
int j;
for (j = 0; j < n; j++) {
max_x[j] = x[j];
}
}
return;
}
if (cur_w + w[i] <= W) { // 左子树:选择第i个物品
x[i] = 1;
dfs(i + 1, cur_w + w[i], cur_v + v[i], x);
x[i] = 0;
}
if (upper_bound(i + 1, cur_w, cur_v) > max_v) { // 右子树:不选第i个物品
dfs(i + 1, cur_w, cur_v, x);
}
}
int main() {
// 读入数据
scanf("%d%d", &n, &W);
int i;
for (i = 0; i < n; i++) {
scanf("%d%d", &w[i], &v[i]);
}
// 初始化最优解
for (i = 0; i < n; i++) {
max_x[i] = 0;
}
// 搜索
int x[MAX_N]; // 当前搜索到的解
dfs(0, 0, 0, x);
// 输出最优解
printf("最优值:%d\n", max_v);
printf("最优解:");
for (i = 0; i < n; i++) {
printf("%d ", max_x[i]);
}
printf("\n");
return 0;
}
```
代码中使用了dfs函数进行搜索,upper_bound函数计算上界,max_x数组记录最优解的每个物品选择情况。注释详细解释了每个函数的作用和实现方式。
阅读全文