用回溯法解决01背包问题c语言程序并打印输出结果

下面是用回溯法解决01背包问题的C语言程序，并输出结果：

#include <stdio.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

void knapsack(int n, int w[], int v[], int W, int *max_value, int x[]) {
    int i, wt = 0, val = 0;
    if (n == 0 || W == 0) {
        *max_value = 0;
        return;
    }
    x[n] = 0;
    knapsack(n-1, w, v, W, &val, x);
    if (w[n] <= W) {
        knapsack(n-1, w, v, W-w[n], &wt, x);
        val += v[n];
    }
    *max_value = max(val, wt);
    if (*max_value == val) {
        x[n] = 0;
    } else {
        x[n] = 1;
    }
}

int main() {
    int n, W, i, max_value;
    printf("Enter the number of items: ");
    scanf("%d", &n);
    int w[n+1], v[n+1], x[n+1];
    printf("Enter the weight and value of each item:\n");
    for (i = 1; i <= n; i++) {
        scanf("%d %d", &w[i], &v[i]);
        x[i] = 0;
    }
    printf("Enter the maximum weight of the knapsack: ");
    scanf("%d", &W);

    knapsack(n, w, v, W, &max_value, x);

    printf("The maximum value that can be obtained is: %d\n", max_value);
    printf("The items selected are: ");
    for (i = 1; i <= n; i++) {
        if (x[i] == 1) {
            printf("%d ", i);
        }
    }
    printf("\n");

    return 0;
}

注：在上述代码中，我们使用了指针来传递最大价值和选中的物品。此外，我们还使用了递归函数来解决01背包问题。