回溯法0-1背包问题代码

好的，下面是回溯法解决0-1背包问题的代码，供您参考：

#include <iostream>
using namespace std;

const int N = 20;
int n, m, ans;
int w[N], v[N];

void dfs(int u, int sum_w, int sum_v) {
    if (sum_w > m) return;
    if (u == n) {
        ans = max(ans, sum_v);
        return;
    }
    dfs(u + 1, sum_w, sum_v);
    dfs(u + 1, sum_w + w[u], sum_v + v[u]);
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> v[i];
    }
    dfs(0, 0, 0);
    cout << ans << endl;
    return 0;
}

在代码中，dfs函数的三个参数分别表示当前考虑到的物品编号、当前已经放入背包的物品的总重量和总价值。在dfs函数中，首先判断当前放入背包的物品的总重量是否超过了背包的容量，如果超过了就直接返回；然后判断是否已经考虑完了所有物品，如果考虑完了就更新最优解；如果还没考虑完就继续递归考虑下一个物品，分别考虑将其放入背包或不放入背包的情况。

希望这段代码对您有所帮助。

相关问题

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

0-1背包问题是一个经典的动态规划问题，但也可以使用回溯法进行求解。

回溯法的基本思路是：从第一个物品开始，依次考虑是否将其放入背包中，递归地考虑剩余的物品，直到所有物品都考虑过为止。

具体来说，可以定义一个回溯函数backtrack，其输入参数包括当前考虑到的物品下标i、当前已经放入背包的物品总价值curValue、当前已经放入背包的物品总重量curWeight、背包总容量capacity、物品价值数组values和物品重量数组weights等。其中，i表示当前要考虑的物品下标，curValue表示当前已经放入背包的物品总价值，curWeight表示当前已经放入背包的物品总重量，capacity表示背包的总容量，values表示每个物品的价值，weights表示每个物品的重量。

在回溯函数中，首先判断是否已经考虑完所有物品，如果是则更新最优解，否则依次考虑将第i个物品放入背包和不放入背包两种情况。如果将第i个物品放入背包后仍然满足背包容量限制，则递归地考虑将后续物品放入背包；如果将第i个物品不放入背包，则直接递归考虑后续物品。最终返回最优解的价值。

下面是使用回溯法求解0-1背包问题的代码实现（假设物品数量为n）：

int max_value = 0;

void backtrack(int i, int curValue, int curWeight, int capacity, int* values, int* weights) {
    if (i == n) {
        if (curValue > max_value) {
            max_value = curValue;
        }
        return;
    }
    if (curWeight + weights[i] <= capacity) {
        backtrack(i + 1, curValue + values[i], curWeight + weights[i], capacity, values, weights);
    }
    backtrack(i + 1, curValue, curWeight, capacity, values, weights);
}

int knapsack(int capacity, int* values, int* weights) {
    max_value = 0;
    backtrack(0, 0, 0, capacity, values, weights);
    return max_value;
}

使用示例：

int main() {
    int capacity = 10;
    int values[] = {6, 3, 5, 4, 6};
    int weights[] = {2, 2, 6, 5, 4};
    int max_value = knapsack(capacity, values, weights);
    printf("max value: %d\n", max_value);
    return 0;
}

输出结果：

max value: 15

在上述示例中，背包总容量为10，物品数量为5，每个物品的价值和重量分别为values和weights数组中的对应元素。程序输出的最大价值为15，表示可以选择将第1、3、5个物品放入背包，总价值为6+5+4=15。

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