回溯法解决0-1背包问题的C语言代码

以下是回溯法解决0-1背包问题的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 cur_w = 0, cur_v = 0;

void dfs(int i)
{
    if (i == n) {
        if (cur_v > best_v)
            best_v = cur_v;
        return;
    }

    if (cur_w + w[i] <= W) {
        cur_w += w[i];
        cur_v += v[i];
        dfs(i + 1);
        cur_w -= w[i];
        cur_v -= v[i];
    }

    dfs(i + 1);
}

int main()
{
    scanf("%d%d", &n, &W);

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

    dfs(0);

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

    return 0;
}

以上是回溯法解决0-1背包问题的C语言代码，其中n为物品个数，W为背包容量，w和v分别表示每个物品的重量和价值。该算法可以求出最大的价值总和。

相关问题

回溯法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。

使用回溯法解决0-1背包问题，并给出c语言代码

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

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

#define MAXN 1000

int n, c;  // 物品数量和背包容量
int w[MAXN], v[MAXN];  // 物品重量和价值
int cw = 0, cv = 0;  // 当前重量和价值
int bestv = 0;  // 最优价值
int x[MAXN];  // 当前解

void backtrack(int i) {
    if (i > n) {
        if (cv > bestv) {
            bestv = cv;
            for (int j = 1; j <= n; ++j) {
                x[j] = w[j];
            }
        }
        return;
    }
    if (cw + w[i] <= c) {
        cw += w[i];
        cv += v[i];
        x[i] = 1;
        backtrack(i+1);
        cw -= w[i];
        cv -= v[i];
    }
    x[i] = 0;
    backtrack(i+1);
}

int main() {
    scanf("%d%d", &n, &c);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &w[i], &v[i]);
    }
    backtrack(1);
    printf("最优价值：%d\n", bestv);
    printf("选中的物品：");
    for (int i = 1; i <= n; ++i) {
        if (x[i]) {
            printf("%d ", i);
        }
    }
    printf("\n");
    return 0;
}

该代码中，backtrack函数是回溯的核心部分，它通过枚举每个物品放或不放来搜索最优解。x数组记录当前选择的物品，bestv记录最优价值。在回溯结束后，输出最优价值和选中的物品即可。