回溯法0-1背包问题c语言

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

#include <stdio.h>

#define MAX_N 100

int n, m; // 物品数量n，背包容量m
int w[MAX_N], v[MAX_N]; // 每个物品的重量w和价值v
int max_v = -1; // 最大价值

void dfs(int i, int weight, int value)
{
    if (i == n) // 所有物品已经考虑完
    {
        if (value > max_v) // 更新最大价值
            max_v = value;
        return;
    }
    if (weight + w[i] <= m) // 如果当前物品可以放入背包
        dfs(i+1, weight+w[i], value+v[i]); // 选择放入当前物品
    dfs(i+1, weight, value); // 不放入当前物品
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &w[i], &v[i]);
    dfs(0, 0, 0); // 从第0个物品开始考虑，当前重量和价值都为0
    printf("%d\n", max_v); // 输出最大价值
    return 0;
}

代码思路：

使用深度优先搜索（DFS）来实现回溯。

每次考虑一个物品，有两种选择：放入背包或不放入背包。如果当前物品可以放入背包，则递归调用dfs(i+1, weight+w[i], value+v[i])；否则递归调用dfs(i+1, weight, value)。当考虑完所有物品后，更新最大价值max_v。