背包问题回溯法C语言实现（手动输入物品价值和数量）

好的，下面是背包问题回溯法的C语言实现，手动输入物品价值和数量：

#include <stdio.h>
#define MAX_N 100

int n, W, max_value;
int w[MAX_N], v[MAX_N], x[MAX_N], cur_x[MAX_N];

void backtrack(int i, int cur_weight, int cur_value) {
    // 边界条件
    if (i == n) {
        if (cur_value > max_value) {
            max_value = cur_value;
            for (int j = 0; j < n; j++) {
                x[j] = cur_x[j];
            }
        }
        return;
    }
    // 不选第i个物品
    backtrack(i + 1, cur_weight, cur_value);
    // 选第i个物品
    if (cur_weight + w[i] <= W) {
        cur_x[i] = 1;
        backtrack(i + 1, cur_weight + w[i], cur_value + v[i]);
        cur_x[i] = 0;
    }
}

int main() {
    // 输入物品数量和背包容量
    printf("请输入物品数量和背包容量：");
    scanf("%d%d", &n, &W);
    // 输入每个物品的重量和价值
    printf("请依次输入每个物品的重量和价值：\n");
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }
    // 回溯求解
    backtrack(0, 0, 0);
    // 输出结果
    printf("背包中物品的最大价值为：%d\n", max_value);
    printf("选择的物品编号为：");
    for (int i = 0; i < n; i++) {
        if (x[i] == 1) {
            printf("%d ", i + 1);
        }
    }
    printf("\n");
    return 0;
}

代码中，首先输入物品数量和背包容量，然后输入每个物品的重量和价值。接着调用回溯函数backtrack，求解背包问题。最后输出背包中物品的最大价值和选择的物品编号。