#include <stdio.h>
#include <stdlib.h>

int best;
int * incumbent;

void testa_solucao(int * V, int n, int W, int * sol, int atual){
  if(W < 0){
    //ultrapassou a capacidade
    return;
  }
  if(atual == n){
    //tenho uma solucao completa
    int valor = 0;
    for(int i = 0; i < n; i++){
      if(sol[i] == 1){ 
        valor = valor + V[i];
      }
      printf("%d, ", sol[i]);
    }
    printf("\n");
    if(valor > best){
      best = valor;
      for(int i = 0; i < n; i++){
        incumbent[i] = sol[i];
      }
    }
    return;
  }
  
  sol[atual] = 1;
  testa_solucao(V, n, W - V[atual], sol, atual + 1);
  
  sol[atual] = 0;
  testa_solucao(V, n, W, sol, atual + 1);
  
  return;
}

int main(int argc, char * argv[]){
  int V[] = {7, 24, 10, 15, 3};
  int n = 5;
  
  int * sol = (int *) malloc(sizeof(int)*n);
  int W = 30;
  
  best = -1;
  incumbent = (int *) malloc(sizeof(int)*n);
  
  testa_solucao(V, n, W, sol, 0);
  
  printf("Melhor sol: ");
  for(int i = 0; i < n; i++){
    printf("%d, ", incumbent[i]);
  }
  printf("\n");
  return 0;
}