Knapsack par recherche exhaustive

knapSack.c

#include"linkedList.h"
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

/*------------------------------------------------------------*/

/*
  Instance d'un probleme de knapSack
*/

typedef struct
{
  /*
    nombre total d'objets
   */
  long nbItems;

  /*
    tableau de nombreObjets elements contenant le poids de 
    chaque element
  */
  long* weights;
  
  /*
    tableau de nombreObjets elements contenant la valeur de 
    chaque element
  */
  long* values;

  /*
    Poids maximum qu'il est possible de placer dans le sac à dos.
   */
  long maxWeight;
}knapSack;

/*------------------------------------------------------------*/

knapSack* knapSackMake(long nbItems, long maxWeight)
{
  knapSack* k = (knapSack*)malloc(sizeof(knapSack));
  k->nbItems = nbItems;
  k->maxWeight = maxWeight;
  k->weights = (long*)malloc(sizeof(long)*nbItems);
  if (k->weights == NULL)
    exit(0);
  k->values = (long*)malloc(sizeof(long)*nbItems);
  if (k->values == NULL)
    exit(0);
  return k;
}

/*------------------------------------------------------------*/

void knapSackSetItem(knapSack* k, long index, long value, long weight)
{
  *(k->weights + index) = weight;
  *(k->values + index) = value;
}

/*------------------------------------------------------------*/

long knapSackValue(knapSack* instance, linkedList* solution)
{
  long res = 0;
  void incrValue(void* i)
    {
      res += *(instance->values  + *((long*)i));
    }
  linkedListApply(solution, incrValue);
  return res;
}

/*------------------------------------------------------------*/

long knapSackWeight(knapSack* instance, linkedList* solution)
{
  long res = 0;
  void incrValue(void* i)
    {
      res += *(instance->weights  + *((long*)i));
    }
  linkedListApply(solution, incrValue);
  return res;
}

/*------------------------------------------------------------*/

int knapSackIsFeasible(knapSack* instance, linkedList* solution)
{
  return knapSackWeight(instance, solution) 
    <= instance->maxWeight;
}

/*------------------------------------------------------------*/

void knapSackPrintInstance(knapSack* k)
{
  long l = 0;
  while(l < k->nbItems)
    {
      printf("(i = %3ld, v = %3ld, w = %3ld)\n", l, 
	     *(k->values + l), *(k->weights + l));
      l++;
    }
  printf("max weight = %ld\n", k->maxWeight); 
}

/*------------------------------------------------------------*/

void knapSackDestroy(knapSack* k)
{
  free(k->values);
  free(k->weights);
  free(k);
}

/*------------------------------------------------------------*/

void* linkedListCopy(void* l)
{
  void* id(void* i)
    {
      return i;
    }
  return linkedListMap((linkedList*)l, id);  
}

/*------------------------------------------------------------*/

void knapSackPrintSolution(linkedList* l)
{
  void printIndex(void* i)
    {
      printf("%ld ", *((long*)i));
    }
  linkedListApply(l, printIndex);  
}

/*------------------------------------------------------------*/

linkedList* knapSackListInit(long n)
{
  linkedList* l; 
  if (n <= 0)
    l = linkedListCreate();
  else
    {
      l = knapSackListInit(n - 1);
      long* p = malloc(sizeof(long));
      if (p == NULL)
	exit(0);
      *p = n-1; 
      linkedListAppend(l, p);
    }
  return l;
}

/*------------------------------------------------------------*/

void knapSackPrintParties(linkedList* l)
{
  void knapSackPrintVoidSolution(void* l)
    {
      printf("[ ");
      knapSackPrintSolution((linkedList*)l);
      printf("]\n");
    }
  linkedListApply(l, knapSackPrintVoidSolution);
}

/*------------------------------------------------------------*/

void doNothing(void* v)
{
}

/*------------------------------------------------------------*/

void destroyInt(void* v)
{
  free((int*)v);
}

/*------------------------------------------------------------*/

void knapSackDestroyParties(linkedList* l)
{
  void destroyPartie(void* p)
    {
      linkedListDestroy((linkedList*)p, doNothing);
    }
  linkedListDestroy(l, destroyPartie);
}

/*------------------------------------------------------------*/

linkedList* parties(linkedList* l)
{
  linkedList* res = linkedListCreate();
  linkedList *partiesWithoutX, *partiesWithX;
  if (linkedListGetSize(l) == 0)
    {
      linkedListAppend(res, linkedListCreate());
    }
  else
    {
      link* x = linkedListUnlinkFirst(l);
      partiesWithoutX = parties(l);
      partiesWithX = linkedListMap(partiesWithoutX, linkedListCopy);
      void appendX(void* data)
	{
	  linkedListAppend((linkedList*)data, x->data);
	}      
      linkedListApply(partiesWithX, appendX);
      linkedListAppendLink(l, x);
      linkedListConcat(res, partiesWithoutX);
      linkedListConcat(res, partiesWithX);
      linkedListDestroy(partiesWithX, doNothing);
      linkedListDestroy(partiesWithoutX, doNothing);
    }
  printf("-> 2^%d\n", linkedListGetSize(l));
  return res;
}

/*------------------------------------------------------------*/

linkedList* knapSackBruteForceSolve(knapSack* k)
{
  linkedList* indexes = knapSackListInit(k->nbItems);
  linkedList* allSolutions = parties(indexes);
  linkedList* bestSolutionSeen = NULL;
  linkedListGetFirst(allSolutions); 
  printf("-> subsets generated.\nTrying to find the best solution\n");
  void findBest(void* v)
    {
      linkedList* l = (linkedList*)v; 
      if (knapSackIsFeasible(k, l) 
	  && (bestSolutionSeen == NULL ||
	      knapSackValue(k, l) > knapSackValue(k, bestSolutionSeen)))
	bestSolutionSeen = l;
    }
  linkedListApply(allSolutions, findBest);
  printf(" -> Done.\nDestroying the subsets\n");
  void* copyInt(void* i)
    {
      void* v = malloc(sizeof(long));
      if (v == NULL)
	exit(0);
      *((long*)v) = *((long*)i);
      return v;
    }
  bestSolutionSeen = linkedListMap(bestSolutionSeen, copyInt);
  void destroyTheLinkedList(void* v)
    {
      linkedListDestroy((linkedList*)v, destroyInt);
    }
  linkedListDestroy(allSolutions, destroyTheLinkedList);
  printf(" -> Done.\nThanks for your patience.\n");
  return bestSolutionSeen;
}

/*------------------------------------------------------------*/

int main()
{
  long t = 21;
  knapSack* k = knapSackMake(t, 40);
  linkedList* s;
  long l;
  for(l = 0 ; l < k->nbItems ; l++)
    knapSackSetItem(k, l, (l*l*l)%10 + 1, (l*l*l*l)%10 + 1);
  knapSackPrintInstance(k);
  s = knapSackBruteForceSolve(k);
  knapSackPrintSolution(s);
  printf("\n");
  linkedListDestroy(s, doNothing);
  knapSackDestroy(k);
  return 0;
}