Problème du sac à dos
Résolu
victorcoasne
Messages postés
1100
Date d'inscription
jeudi 24 avril 2003
Statut
Membre
Dernière intervention
17 octobre 2012
-
29 déc. 2008 à 22:16
victorcoasne Messages postés 1100 Date d'inscription jeudi 24 avril 2003 Statut Membre Dernière intervention 17 octobre 2012 - 7 janv. 2009 à 14:58
victorcoasne Messages postés 1100 Date d'inscription jeudi 24 avril 2003 Statut Membre Dernière intervention 17 octobre 2012 - 7 janv. 2009 à 14:58
A voir également:
- Problème du sac à dos python
- Problème du sac à dos exercices corrigés python - Meilleures réponses
- Probleme sac a dos python - Meilleures réponses
- Probleme du sac a dos Avec répétition ou "Knapsack with repetition" - Forum C++ & C++ .NET
- Probleme du sac a dos en C - Forum C / C++ / C++.NET
- Le probleme de sac a dos ✓ - Forum Java
- Mastermind python - Forum Python
- Revenir à la ligne python - Forum Python
22 réponses
coucou747
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Membre
Dernière intervention
30 juillet 2012
44
7 janv. 2009 à 13:21
7 janv. 2009 à 13:21
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
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