背包问题回溯法 C语言

背包问题是一个经典的组合优化问题，在计算机科学中非常重要。它的主要思想是将一个重量为W的背包和N个不同重量、不同价值的物品放入其中，如何使得这个背包中所装物品的总价值最大。

回溯法是解决该问题的一种常用方法。其基本思路是从所有可能的物品中选择一个物品放入背包，然后对剩下的物品进行选择，直到所有物品都被考虑过一遍，得到一个解。如果该解是最优解，则结束搜索；否则，回溯到上一步选择另一个物品，并继续进行搜索。这里需要注意的是，在搜索过程中需要剪枝，以排除那些不可能达到最优解的情况。

以下是一个C语言实现背包问题回溯法的示例代码：

#include <stdio.h>

#define MAX_N 100

int n, W; // 物品数，背包容量
int w[MAX_N], v[MAX_N]; // 物品重量，物品价值
int max_v; // 最大价值

// 剪枝函数
void dfs(int i, int sum_w, int sum_v) {
    if (i == n) { // 已经考虑完所有物品
        if (sum_w <= W && sum_v > max_v) { // 更新最大价值
            max_v = sum_v;
        }
        return;
    }

    // 选择第i个物品
    dfs(i+1, sum_w+w[i], sum_v+v[i]);

    // 不选择第i个物品
    dfs(i+1, sum_w, sum_v);
}

int main() {
    scanf("%d%d", &n, &W);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }

    max_v = 0;
    dfs(0, 0, 0);

    printf("%d\n", max_v);

    return 0;
}