#include <stdio.h>

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

void knapsack_backtracking(int values[], int weights[], int capacity, int n,
                           int current_value, int current_weight,
                           int item_index, int solution[], int best_solution[],
                           int *best_value) {
    if (item_index == n || current_weight == capacity) {
        if (current_value > *best_value) {
            *best_value = current_value;
            for (int i = 0; i < n; i++) {
                best_solution[i] = solution[i];
            }
        }
        return;
    }

    // Exclude the current item
    knapsack_backtracking(values, weights, capacity, n, current_value, current_weight,
                          item_index + 1, solution, best_solution, best_value);

    // Include the current item if it doesn't exceed the capacity
    if (current_weight + weights[item_index] <= capacity) {
        solution[item_index] = 1;
        knapsack_backtracking(values, weights, capacity, n, current_value + values[item_index],
                              current_weight + weights[item_index], item_index + 1,
                              solution, best_solution, best_value);
        solution[item_index] = 0;
    }
}

int main() {
    int values[] = {7, 4, 2, 9, 4, 5};
    int weights[] = {3, 3,1, 1,2 ,1};
    int capacity = 10;
    int n = sizeof(values) / sizeof(values[0]);

    int best_value = 0;
    int best_solution[n];
    int solution[n];

    knapsack_backtracking(values, weights, capacity, n, 0, 0, 0, solution, best_solution, &best_value);

    printf("Best value: %d\n", best_value);
    printf("Best solution (selected items): ");
    for (int i = 0; i < n; i++) {
        printf("%d ", best_solution[i]);
    }
    printf("\n");

    return 0;
}