分支限界解决01背包问题

分支限界法是一种用于求解组合优化问题的搜索算法，特别适用于求解背包问题等动态规划问题。在01背包问题中，每个物品都有一个重量和一个价值，目标是在不超过背包总容量的情况下，选择一些物品使得它们的总价值最大。

01背包问题的分支限界解法通常采用回溯法，遵循以下步骤：

1. **状态定义**：定义一个二元数组 `dp[i][w]`，表示在容量为 `w` 的情况下，前 `i` 个物品的最大价值。

2. **初始化**：对于每个物品 `i`，设 `dp[i]` 为不选第 `i` 个物品的价值（即 0）。

3. **搜索过程**：
- 对于当前状态 `dp[i][w]`，如果 `w` 大于当前物品的重量 `weight[i]`，则可以考虑选择或不选择该物品。
- 如果选择（`include`），则更新 `dp[i][w]` 为 `value[i] + dp[i-1][w-weight[i]]`；
- 如果不选择（`exclude`），则保持 `dp[i][w]` 为上一个状态的值，即 `dp[i-1][w]`。
- 将两个可能的决策分支记录下来，分别递归检查剩余的物品和容量。

4. **剪枝**：使用限界条件（如当前物品的价值小于剩余容量的价值，肯定不会选择这个物品），避免搜索无效的子树。

5. **回溯**：当所有可能的物品都被考虑过或达到背包容量上限时，回溯到上一个状态并尝试其他选择。

6. **最优解**：最终 `dp[n][W]` 中的 `n` 是物品数量，`W` 是背包容量，就是最大的价值。

相关问题

c语言分支限界解决01背包问题

以下是使用C语言分支限界法解决01背包问题的示例代码：

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

#define MAX_N 1000

typedef struct {
    int w; // 物品重量
    int v; // 物品价值
} Item;

typedef struct {
    int id; // 节点编号
    int w; // 当前背包重量
    int v; // 当前背包价值
    int bound; // 当前节点的价值上界
} Node;

int n; // 物品数量
int c; // 背包容量
Item items[MAX_N]; // 物品数组
int bestv; // 最优解的价值
int bestx[MAX_N]; // 最优解的解向量

// 比较函数，用于qsort排序
int cmp(const void *a, const void *b) {
    Item *ia = (Item *)a;
    Item *ib = (Item *)b;
    double va = (double)ia->v / ia->w;
    double vb = (double)ib->v / ib->w;
    return vb > va ? 1 : vb < va ? -1 : 0;
}

// 计算节点的价值上界
int bound(Node *node) {
    if (node->w >= c) {
        return 0;
    }
    int bound = node->v;
    int j = node->id + 1;
    int w = node->w;
    while (j < n && w + items[j].w <= c) {
        w += items[j].w;
        bound += items[j].v;
        j++;
    }
    if (j < n) {
        bound += (c - w) * items[j].v / items[j].w;
    }
    return bound;
}

// 分支限界法求解01背包问题
void knapsack() {
    // 按单位重量价值从大到小排序
    qsort(items, n, sizeof(Item), cmp);

    // 初始化根节点
    Node root = { -1, 0, 0, 0 };
    Node *p = &root;

    // 初始化最优解
    for (int i = 0; i < n; i++) {
        bestx[i] = 0;
    }

    // 初始化堆
    MaxHeap heap;
    initMaxHeap(&heap);

    // 将根节点插入堆中
    insertMaxHeap(&heap, p);

    // 不断取出堆顶节点进行扩展，直到堆为空或者堆顶节点的价值上界小于等于当前最优解的价值
    while (!isEmptyMaxHeap(&heap)) {
        // 取出堆顶节点
        p = deleteMaxHeap(&heap);

        // 如果当前节点的价值上界小于等于当前最优解的价值，则剪枝
        if (p->bound <= bestv) {
            continue;
        }

        // 扩展左儿子节点
        Node left = { p->id + 1, p->w + items[p->id + 1].w, p->v + items[p->id + 1].v, 0 };
        left.bound = bound(&left);
        if (left.w <= c && left.v > bestv) {
            bestv = left.v;
            for (int i = 0; i <= left.id; i++) {
                bestx[i] = 0;
            }
            bestx[left.id] = 1;
        }
        if (left.bound > bestv) {
            insertMaxHeap(&heap, &left);
        }

        // 扩展右儿子节点
        Node right = { p->id + 1, p->w, p->v, 0 };
        right.bound = bound(&right);
        if (right.bound > bestv) {
            insertMaxHeap(&heap, &right);
        }
    }
}

int main() {
    // 读入物品数量和背包容量
    scanf("%d%d", &n, &c);

    // 读入物品重量和价值
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &items[i].w, &items[i].v);
    }

    // 求解01背包问题
    knapsack();

    // 输出最优解的价值和解向量
    printf("最优解的价值为：%d\n", bestv);
    printf("最优解的解向量为：");
    for (int i = 0; i < n; i++) {
        printf("%d ", bestx[i]);
    }
    printf("\n");

    return 0;
}

用分支限界解决01背包问题

01背包问题是一个经典的动态规划（Dynamic Programming, DP）问题，但也可以使用分枝定界法（Branch and Bound）来求解。这种方法特别适用于那些有大量状态且可能存在最优解下界的情况，比如背包问题中的每个物品都有一个价值和一个重量。

在01背包问题中，给定一组物品，每种物品有一个固定的价值和重量，以及一个总背包容量。我们需要决定是否选择某一种物品放入背包，以使背包中的总价值最大，但不超过背包容量。

分支限界法的基本思路如下：

1. **定义搜索空间**：对于每个物品i，我们可以选择将其放入背包（取值为1），或不放（取值为0）。这构成了问题的子节点。

2. **设置上界**：对于每个子节点，我们维护当前状态下可能的最大价值（即上界），可以通过已知的子问题结果计算得到。

3. **剪枝**：如果当前节点的上界小于当前最优解，那么这个子树不可能产生更好的解决方案，可以直接剪掉，节省搜索时间。

4. **分支操作**：根据剩余物品继续递归地生成子节点，直到达到某个基本情况（所有物品都考虑过，或者背包容量为0）。

5. **回溯和更新最优解**：在搜索过程中，如果找到一个更大的价值，就更新全局最优解。

下面是分支限界法的一个简化版伪代码示例：

bool isFeasible(int weight, int capacity) {
    return weight <= capacity;
}

int knapsackBranchBound(vector<int>& values, vector<int>& weights, int maxWeight, int& bestSolution, vector<bool>& taken) {
    if (maxWeight == 0 || taken.empty()) {
        return 0; // 基本情况，空背包或没有物品
    }
    
    int solution = 0;
    bool foundBetterSolution = false;

    for (int i = 0; i < taken.size(); ++i) {
        taken[i] = false; // 不选物品
        if (isFeasible(weights[i], maxWeight)) {
            solution = std::max(solution, knapsackBranchBound(values, weights, maxWeight - weights[i], bestSolution, taken));
            if (solution > bestSolution) {
                bestSolution = solution;
                foundBetterSolution = true;
            }
        }

        taken[i] = true; // 选物品
        if (isFeasible(weights[i], maxWeight)) {
            solution = std::max(solution, values[i] + knapsackBranchBound(values, weights, maxWeight - weights[i], bestSolution, taken));
            if (solution > bestSolution) {
                bestSolution = solution;
                foundBetterSolution = true;
            }
        }
    }

    if (!foundBetterSolution) {
        return bestSolution; // 没有更好的解，返回当前最佳
    } else {
        return solution; // 继续搜索
    }
}