Problème du sac à dos [Résolu]

victorcoasne 1100 Messages postés jeudi 24 avril 2003Date d'inscription 17 octobre 2012 Dernière intervention - 29 déc. 2008 à 22:16 - Dernière réponse : victorcoasne 1100 Messages postés jeudi 24 avril 2003Date d'inscription 17 octobre 2012 Dernière intervention
- 7 janv. 2009 à 14:58
Bonjour,

J'ai deux sacs à dos de n emplacements.
Je dois placer n*2 objets de masse différentes.
Il faut équilibrer un maximum pour que la différence soit minimale et pour éviter de faire basculer l'âne sur lequel je vais mettre les sacs.

J'ai tout de suite pensé au problème du sac à dos et en cherchant j'ai pensé que la solution du problème Sac à dos multiple de même contenance aussi appellé MKP-I mais je n'ai pas trouvé de solution pour résoudre cet exercice.

Merci de me donner des pistes, des solutions car après de longues recherches je n'ai toujours rien trouvé.

Merci d'avance et bonne prog,
Joyeuses fêtes de fin d'année !
@++

Victor
Afficher la suite 

22 réponses

Répondre au sujet
coucou747 12336 Messages postés mardi 10 février 2004Date d'inscription 30 juillet 2012 Dernière intervention - 7 janv. 2009 à 13:21
+1
Utile
Salut

on suppose que la fonction "algo" resout le probleme

tu peux commencer par faire des majorations (pour restreindre les recherches)

/* majoration */
int maj1(int *v, int n){ /* v doit-etre decroissant*/
    int i;
    int s=0;
    for (i=0;i<2*n;i+=2){
        s += v[i] - v[i+1]; /* c'est positif*/
        if (s > 0) s *= -1;
    }
    return abs(s);
}

cette majoration est naive, elle prend une liste TRIEE, et met le plus gros d'un cote, le suivant de l'autre, et recommence l'operation.

on peut aussi faire une majoration "dichotomique"

c'est a dire qu'on divise le probleme en deux sous problemes de taille n /2 (beaucoup plus rapides a resoudre), et on se sert des resultats des sous problemes pour faire l'arrangement

int maj2(int *v, int n){ /* v doit-etre decroissant*/
    int i=n/2;
    int a = algo(v, i);
    int b = algo(v + i, n - i);
    if (a > b){
        return a - b;
    }else{
        return b - a;
    }
}

voici un algo naif qui se contente de tester toutes les possibilites :
v est la liste des poids
n2 le nombre d'elements
l le nombre d'elements a mettre a gauche
r le nombre d'elements a mettre a droite
somme la somme des elements precedents
int loopnaif(int *v, int n2, int l, int r, int somme){    if (l -1 || r -1 ) return INT_MAX;
    if (n2 == 0) return abs(somme);
    return min(
        loopnaif(v+1, n2-1, l-1, r, somme - v[0]),
        loopnaif(v+1, n2-1, l, r-1, somme + v[0])
    );
}
l'appel de notre boucle naive.
int algonaif(int *v, int n){
    return loopnaif(v, n*2, n, n, 0);   
}

on peut affiner cet algo en prennant en compte les majorations :

/* algo intelligent */
int loop(int *v, int *b, int score, int n2, int l, int r, int somme){    if (l -1 || r -1 ) return score;
    if (n2 == 0) return min(score, abs(somme));
    if (
        (somme > 0 && (score < somme - b[0]))
        || (somme < 0 && (score > somme + b[0]))
    ){
        /* printf("%d %d %d \n", score, somme, *b); */
        return score;
    }
    if (somme > 0){ /* on cherche a examiner le meilleur cas en premier,
    ca permet de couper plus de branches */
        score = loop(v+1, b+1, score, n2-1, l-1, r, somme - v[0]);
        return loop(v+1, b+1, score, n2-1, l, r-1, somme + v[0]);
    }else{
        score = loop(v+1, b+1, score, n2-1, l, r-1, somme + v[0]);
        return loop(v+1, b+1, score, n2-1, l-1, r, somme - v[0]);
    }
}
int algo(int *v, int n){
    int *bouge = malloc(sizeof(int) * 2 * n);

    int i, j;
    int score, score2;
    score maj1(v, n); /* printf("maj1 %d\n", score); */
    if (n>18){        score2 maj2(v, n); /* printf("maj2 %d\n", score2); */
        if (score2 < score){ score = score2; }
    }
    if (score){

        for (i=0;i<2*n;i++) bouge[i]=0;
        for (i=0;i<2*n;i++) for (j=i;j>=0;j--) bouge[j]+=v[i];

        score = loop(v+1, bouge+1, score, n*2-1, n, n-1, v[0]);
    }
    free(bouge);
    return score;
}

ca revient a dire : quand on est trop loin des majorations, on abandonne

VOILA, ca c'etait pour l'algorithmique, maintenant, place a l'heuristique :

on peut placer dans un ordre "intuitutif" les nombres (comme on le faisait au debut) puis tester des inversions de nombres pour pouvoir faire les inversions interessantes.

ce code fonctionne beaucoup plus rapidement que l'algo precedent, et apporte des solutions (bien que non exactes) BEAUCOUP plus proches des bonnes que les premieres majorations.

voici le code de l'heuristique :

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

int min(int a, int b){
  if (a<b) return a;
  return b;
}

int cmp_int(const void * a, const void *b){
  return *(int*)b - *(int*)a;
}

void swap(int* v, int i, int j){  int a v[i]; v[i] v[j]; v[j] = a;
}

int score(int *v, int n){
  int i;
  int s = 0;
  for (i=0;i<n;i++){
    s += v[i] - v[n+i];
  }
  return s;
}

int * shuffle_tarot(int *v, int n){
  int *bouge = malloc(sizeof(int) * 2 * n);
  int i;
  for (i=0;i<n;i++){
    bouge[i] = v[2*i];
    bouge[n+i] = v[2*i+1];
  }
  return bouge;
}

int shuffle(int *v, int n){
  int s = score(v, n);
  int n2 = 2*n;
  int i, j, d;
  startloop:
  for (i=0;i<n;i++){
    for(j=n;j<n2;j++){
      d = 2 * (v[j] - v[i]);
      if ( abs(s + d ) < abs(s) ){
    swap(v, i, j);
    s += d;
    goto startloop;
      }
    }
  }
  return abs(s);
}

int algo_bubble(int *v, int n){
  qsort(v, 2*n, sizeof(int), cmp_int);
  int * t = shuffle_tarot(v, n);
  int s = shuffle(v, n);
  return s;
}

int main(){
  int n, i;
  int *v;
  scanf("%d\n", &n);
  v = malloc(sizeof(int) * 2 * n);
  for (i=0;i<2*n;i++)
    if (scanf("  %d ", &v[i]) == -1){
      printf("entree invalide\n");
      exit(1);
    }
  printf("%d\n", algo_bubble(v, n));
  free(v);
  return 0;
}

la fonction shuffle n'etait pas suffisante : inverser une fois c'est bien, mais deux fois c'est mieux (on teste par paquets de deux inversions)


int shuffle(int *v, int n){

  int s = score(v, n);

  int n2 = 2*n;

  int i, j, k, l, d1, d2;

  startloop:

  for (i=0;i<n;i++){

    for(j=n;j<n2;j++){

      d1 = 2 * (v[j] - v[i]);

      for (k=i+1;k<n;k++){

    for(l=j+1;l<n2;l++){

      d2 = 2 * (v[l] - v[k]);

      if ( abs(s + d1 +d2 ) < abs(s) ){

        swap(v, i, j);

        swap(v, k, l);

        s += d1+d2;

        goto startloop;

      }

    }

      }

      if ( abs(s + d1 ) < abs(s) ){

    swap(v, i, j);

    s += d1;

    goto startloop;

      }

    }

  }

  return abs(s);

}

voila
Cette réponse vous a-t-elle aidé ?  
Commenter la réponse de coucou747
coucou747 12336 Messages postés mardi 10 février 2004Date d'inscription 30 juillet 2012 Dernière intervention - 29 déc. 2008 à 23:21
0
Utile
c'est cool prologin.
Commenter la réponse de coucou747
victorcoasne 1100 Messages postés jeudi 24 avril 2003Date d'inscription 17 octobre 2012 Dernière intervention - 30 déc. 2008 à 14:28
0
Utile
Bonjour,

Personne pour donner une piste une une documentation sur le sac à dos multiple de même contenance ?

Merci et bonne prog,
@++

Victor
Commenter la réponse de victorcoasne
coucou747 12336 Messages postés mardi 10 février 2004Date d'inscription 30 juillet 2012 Dernière intervention - 30 déc. 2008 à 14:36
0
Utile
salut

demander sur CodeS-SourceS une solution pour un exercice de prologin, je trouve ca assez gonfle...

je te donnerais la solution le 5 janvier, quand les soumissions du QCM seront passees
Commenter la réponse de coucou747
victorcoasne 1100 Messages postés jeudi 24 avril 2003Date d'inscription 17 octobre 2012 Dernière intervention - 30 déc. 2008 à 14:47
0
Utile
Bonjour,

Je ne cherche pas un exo de prologin mais des pistes pour un exos que j'ai à faire pour mon prof d'algo.

Merci et bonne prog,
@++

Victorhttp://www.victorlogiciels.com
Commenter la réponse de victorcoasne
coucou747 12336 Messages postés mardi 10 février 2004Date d'inscription 30 juillet 2012 Dernière intervention - 30 déc. 2008 à 14:53
0
Utile
http://www.prologin.org/?q=contest/qcm/2009/view

tout en bas, c'est exactement le meme exercice
Commenter la réponse de coucou747
victorcoasne 1100 Messages postés jeudi 24 avril 2003Date d'inscription 17 octobre 2012 Dernière intervention - 30 déc. 2008 à 15:18
0
Utile
Bonjour,

Ah ouai en différent mais c'est le même.

Dans ce cas donne juste des pistes, je comprends qu'il ne faut pas donner la solution avant la fin du QCM.

Merci et bonne prog,
@++

Victorhttp://www.victorlogiciels.com
Commenter la réponse de victorcoasne
coucou747 12336 Messages postés mardi 10 février 2004Date d'inscription 30 juillet 2012 Dernière intervention - 30 déc. 2008 à 15:29
0
Utile
c'est un probleme np complet qui a une solution dynamique en O( n * somme des valeurs )

le principe etant de placer n elements parmi 2n elements, de facon a ce que la somme de leurs poids ne depasse pas (somme des valeurs) /2
Commenter la réponse de coucou747
victorcoasne 1100 Messages postés jeudi 24 avril 2003Date d'inscription 17 octobre 2012 Dernière intervention - 30 déc. 2008 à 16:37
0
Utile
Bonjour,

Je m'étais dis ça aussi.
Du coups j'avais rempli les sacs en classant les poids en décroissance et en mettant dans un sac en déficit de poids le poids suivant.
Mais cette méthode ne prend pas en compte la compensation pour certain cas.
Après j'avais fait l'algo glouton pour remplir un sac (de capacité somme des valeurs / 2) et mis le reste ainsi que les plus petits excédents du premier sac dans le second mais ça ne marchait toujours pas.

Et puis j'ai pas de livre d'algo parlant des problème np complet.
Les docs que j'ai trouvé sont en anglais et je sais même pas si elles correspondent à ce qui me faut.
Les maths algorithmique en anglais c'est pas facile à lire.

Merci pour tes pistes constructives mais ce que tu m'as dit je l'avais trouvé.
N'aurais-tu pas d'autres pistes ?

Merci et bonne prog,
@++

Victorhttp://www.victorlogiciels.com
Commenter la réponse de victorcoasne
victorcoasne 1100 Messages postés jeudi 24 avril 2003Date d'inscription 17 octobre 2012 Dernière intervention - 30 déc. 2008 à 16:41
0
Utile
Bonjour,

J'ai oublié de dire que j'avais fait du récursif en évitant de prendre toutes les possibilités mais en prenant seulement les possibilités possibles un peu à la manière des algo génétique mais sans stocker ça en mémoire mais par exemple pour 40 objets on a 2* 68923264410 possibilités (j'en élimine la moitié car si on met par exemple 2+3 dans le sac A et 4+5 dans le sac B ça revient à mettre 4+5 dans le sac A et 2+3 dans le B).

Merci et bonne prog,
@++

Victorhttp://www.victorlogiciels.com
Commenter la réponse de victorcoasne
victorcoasne 1100 Messages postés jeudi 24 avril 2003Date d'inscription 17 octobre 2012 Dernière intervention - 6 janv. 2009 à 10:54
0
Utile
Bonjour,

"je te donnerais la solution le 5 janvier"
> On est le 6 janvier mais tu n'a pas posté la réponse.

Merci et bonne prog,
@++

Victorhttp://www.victorlogiciels.com
Commenter la réponse de victorcoasne
coucou747 12336 Messages postés mardi 10 février 2004Date d'inscription 30 juillet 2012 Dernière intervention - 6 janv. 2009 à 11:32
0
Utile
j'ai recu un mail de prologin :

Nous avons décidé de vous laisser quelques jours supplémentaires pour
rendre votre QCM de sélection. Tu as désormais jusqu'à mardi, 23h42,
Commenter la réponse de coucou747
victorcoasne 1100 Messages postés jeudi 24 avril 2003Date d'inscription 17 octobre 2012 Dernière intervention - 6 janv. 2009 à 11:34
0
Utile
Bonjour,

Et mercredi on prolonge encore ?

Merci et bonne prog,
@++

Victorhttp://www.victorlogiciels.com
Commenter la réponse de victorcoasne
coucou747 12336 Messages postés mardi 10 février 2004Date d'inscription 30 juillet 2012 Dernière intervention - 6 janv. 2009 à 11:38
0
Utile
j'y suis pour rien...

sur ton profil, on peut lire que t'as moins de 21 ans, donc tu peux faire prologin, et vu que ton exo est exactement celui de prolo, jvais pas te donner une solution hein...
Commenter la réponse de coucou747
victorcoasne 1100 Messages postés jeudi 24 avril 2003Date d'inscription 17 octobre 2012 Dernière intervention - 6 janv. 2009 à 11:45
0
Utile
Bonjour,

Oui normal que tu doûtes que je cherche pas l'exercice pour prologin.
ça me paraissait bizard qu'un concours qui a une date précise soit reporté.

Mais si ça ne dépend pas de toi j'attendrai.

Merci et bonne prog,
@++

Victorhttp://www.victorlogiciels.com
Commenter la réponse de victorcoasne
coucou747 12336 Messages postés mardi 10 février 2004Date d'inscription 30 juillet 2012 Dernière intervention - 6 janv. 2009 à 12:17
0
Utile
euh... non, au contraire, moi je suis percuade que tu fais ca pour prolo (sinon, pourquoi ca serait le meme exo...)

moi je ne suis pas a l'asso prologin, je suis simple candidat, j'imagine qu'ils n'ont pas recu beaucoup de questionnaires, donc ils ont laisse plus de temps.
Commenter la réponse de coucou747
victorcoasne 1100 Messages postés jeudi 24 avril 2003Date d'inscription 17 octobre 2012 Dernière intervention - 6 janv. 2009 à 12:44
0
Utile
Bonjour,

Je me cite : "Je ne cherche pas un exo de prologin mais des pistes pour un exos que j'ai à faire pour mon prof d'algo."

Merci et bonne prog,
@++

Victorhttp://www.victorlogiciels.com
Commenter la réponse de victorcoasne
victorcoasne 1100 Messages postés jeudi 24 avril 2003Date d'inscription 17 octobre 2012 Dernière intervention - 7 janv. 2009 à 13:42
0
Utile
Bonjour,

ça fait beaucoup de choses tout ça.

Mais est-ce que y'a un algo qui dit toujours la bonne réponse.
Quand tu parles d'heuristique tu dis que c'est approché.
Et que le premier algo (proche d'une solution que j'ai proposé) n'indique pas toujours la meilleur réponse.

Merci et bonne prog,
@++

Victorhttp://www.victorlogiciels.com
Commenter la réponse de victorcoasne
coucou747 12336 Messages postés mardi 10 février 2004Date d'inscription 30 juillet 2012 Dernière intervention - 7 janv. 2009 à 14:08
0
Utile
si t'avais pris le temps de lire, t'aurais vu que :

int algo(int *v, int n) et int algonaif(int *v, int n)

donnent des solutions exactes
Commenter la réponse de coucou747
victorcoasne 1100 Messages postés jeudi 24 avril 2003Date d'inscription 17 octobre 2012 Dernière intervention - 7 janv. 2009 à 14:30
0
Utile
Bonjour,

J'ai bien lu mais le naïf c'est du récursif et il prend trop de temps pour de grandes valeurs.
L'autre j'ai pas encore bien analysé.

Merci et bonne prog,
@++

Victorhttp://www.victorlogiciels.com
Commenter la réponse de victorcoasne

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Problème du sac à dos - page 2