回溯法求0/1背包问题c++代码

以下是回溯法求0/1背包问题的c代码:

#include <stdio.h>

int n, max_weight;
int weight[100], value[100];
int selected_items[100];
int max_value = 0;

void backtrack(int k, int current_weight, int current_value);

int main(){
    printf("请输入物品数量:");
    scanf("%d", &n);
    printf("请输入背包容量:");
    scanf("%d", &max_weight);
    for(int i = 0; i < n; i++){
        printf("请输入物品%d的重量和价值:", i+1);
        scanf("%d %d", &weight[i], &value[i]);
    }
    backtrack(0, 0, 0);
    printf("能够获得的最大价值为%d\n", max_value);
    printf("选中的物品为:");
    for(int i = 0; i < n; i++){
        if(selected_items[i] == 1)
            printf(" %d", i+1);
    }
    printf("\n");
    return 0;
}

void backtrack(int k, int current_weight, int current_value){
    if(k == n){
        if(current_weight <= max_weight && current_value > max_value){
            max_value = current_value;
            for(int i = 0; i < n; i++){
                selected_items[i] = 0;
                if(weight[i] + current_weight <= max_weight && value[i] + current_value == max_value)
                    selected_items[i] = 1;
            }
        }
        return;
    }
    if(current_weight + weight[k] <= max_weight)
        backtrack(k+1, current_weight+weight[k], current_value+value[k]);
    backtrack(k+1, current_weight, current_value);
}