C语言分支限界法求解01背包问题_分支限界法解决0-1背包问题

分支限界法是一种求解优化问题的算法，针对01背包问题，它可以通过在搜索过程中剪枝，减少搜索空间的大小，提高算法的效率。

具体来说，分支限界法会将当前状态下的可行解集合分成若干个子集，每个子集代表一条搜索路径，然后根据某种启发式策略（如最大价值优先、最小重量优先等）对这些子集进行排序，选择价值最大/重量最小的子集进行扩展，将其分成若干个子集，再重复上述过程，直到找到最优解或者搜索结束。

在求解01背包问题时，分支限界法每次扩展节点时，会判断当前节点能否产生更优的解，如果不能，就进行剪枝，减少搜索空间。例如，如果当前节点已经超出了背包的容量限制，就可以直接剪枝，不再继续扩展。在搜索过程中，分支限界法还会维护一个上界，即当前可行解集合中的最优解，如果当前节点的下界已经小于上界，也可以直接剪枝，不再继续扩展。

分支限界法是一种高效、精确的求解优化问题的算法，但需要注意的是，它并不保证一定能找到最优解，因为搜索空间较大时，其时间复杂度可能会非常高。

代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 1000  // 最大物品数量
#define MAX_W 1000  // 最大背包容量

int n;  // 物品数量
int w[MAX_N];  // 物品重量
int v[MAX_N];  // 物品价值
int c;  // 背包容量
int maxv;  // 最大价值
int curw;  // 当前背包重量
int curv;  // 当前背包价值
int bestv[MAX_W];  // bestv[i]表示当前索引为i时，背包容量为i时的最大价值

// 计算以j为索引、背包容量为c的情况下，能够获得的最大价值
int bound(int j, int c) {
    int b = curv;
    int leftw = c - curw;
    while (j < n && leftw >= w[j]) {
        leftw -= w[j];
        b += v[j];
        j++;
    }
    if (j < n) {
        b += leftw * v[j] / w[j];
    }
    return b;
}

// 搜索第i个物品是否放入背包
void dfs(int i) {
    if (i == n) {  // 达到叶子节点，更新最大价值
        maxv = curv;
        return;
    }
    // 不选第i个物品
    bestv[i+1] = bound(i+1, c);  // 计算下一个物品的最大价值
    if (bestv[i+1] < maxv) {  // 如果最大价值都小于当前最大价值，直接返回
        return;
    }
    dfs(i+1);
    // 选第i个物品
    if (curw + w[i] <= c) {  // 可以放入背包
        curw += w[i];
        curv += v[i];
        if (curv > maxv) {  // 更新最大价值
            maxv = curv;
        }
        bestv[i+1] = bound(i+1, c);  // 计算下一个物品的最大价值
        if (bestv[i+1] > maxv) {  // 如果最大价值比当前最大价值大，继续搜索
            dfs(i+1);
        }
        curw -= w[i];  // 回溯
        curv -= v[i];
    }
}

int main() {
    // 读入数据
    scanf("%d%d", &n, &c);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }
    // 初始化
    maxv = curv = 0;
    curw = 0;
    bestv[0] = bound(0, c);
    // 搜索
    dfs(0);
    // 输出结果
    printf("%d\n", maxv);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

分支限界法的思路如下：

1. 按照某种规则先对问题求出一个下界，把问题分成可行和不可行两种情况。对于可行的情况，可以计算出对应的最优解的上界（贪心法、动态规划等）。
2. 依次搜索所有可能的解，在搜索过程中，利用计算出的上界剪枝，即当某个节点的上界小于当前最优解时，可以直接返回上一层，省略掉这个分支。
3. 在搜索过程中，记录当前的最优解，并不断更新。当达到叶子节点，即搜索结束时，返回最优解。

对于01背包问题，每个节点有两种情况，即选或不选当前物品。对于每个节点，可以计算出剩余物品的最大价值，从而计算出当前节点可以达到的最大价值（上界）。用一个数组bestv记录每个节点的最大价值，如果当前节点的上界小于当前最优解，直接返回；如果当前节点的最大价值比当前最优解大，继续搜索。在搜索过程中，使用变量curw和curv记录当前的背包重量和价值，变量maxv记录当前的最大价值。