背包问题回溯算法c语言

背包问题是一个经典的动态规划问题，不过也可以使用回溯算法来解决。

回溯算法的基本思想是将问题分解成若干个子问题，然后依次解决这些子问题，直到最终得到解。在背包问题中，我们可以将问题分解为选或不选每个物品，然后通过不断试探来得到最优解。

下面是使用回溯算法解决背包问题的C语言代码：

#include <stdio.h>

#define MAX_N 100
#define MAX_W 1000

int n, W; // 物品数量和背包容量
int w[MAX_N], v[MAX_N]; // 物品的重量和价值
int best_v = 0; // 最优解

// 计算总价值
int total_v(int *x) {
    int tv = 0;
    for (int i = 0; i < n; i++) {
        tv += x[i] * v[i];
    }
    return tv;
}

// 回溯算法
void backtrack(int *x, int i, int cw) {
    if (i == n) { // 已经选择完所有物品
        int tv = total_v(x); // 计算总价值
        if (tv > best_v) { // 更新最优解
            best_v = tv;
        }
        return;
    }
    if (cw + w[i] <= W) { // 选择第i个物品
        x[i] = 1;
        backtrack(x, i + 1, cw + w[i]);
    }
    x[i] = 0; // 不选择第i个物品
    backtrack(x, i + 1, cw);
}

int main() {
    int x[MAX_N] = {0}; // 选或不选物品的状态
    scanf("%d %d", &n, &W);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &w[i], &v[i]);
    }
    backtrack(x, 0, 0);
    printf("%d\n", best_v);
    return 0;
}

在这个代码中，我们使用了一个长度为n的数组x来记录每个物品是否被选中，1表示选择，0表示不选择。backtrack函数中的i表示当前考虑的物品，cw表示当前背包中物品的总重量。在回溯过程中，如果当前背包容量还可以装下第i个物品，我们就尝试选择这个物品，然后递归调用backtrack函数。如果背包容量不够，我们就不选择这个物品，然后继续递归调用backtrack函数。当i=n时，表示已经选择完所有物品，我们计算总价值，并更新最优解。

这个算法的时间复杂度是指数级别的，因为需要对每个物品都进行选或不选两种情况的试探，所以当物品数量较大时，效率会很低。