1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| Supposons qu'on travaille, pour fixer les idées avec 5 objets
dont les poids sont : 12,4,2,1,1
et dont les valeurs sont 4,10,2,2,1
On ne fait que reprendre l'exemple du Wiki avec le poids maximum =15
L'idée est de combiner trois approches données dans l'article pour générer un arbre des 'possibles' aussi réduit que possible.
Une 'possibilité' est donc une suite arbitraire de 5 éléments binaires
par exemple {1,0,1,0,1}
Pour chaque possibilité on peut donc calculer le poids et la valeur.
Le problème est que les possibilités sont en trop grand nombre pour les générer toutes, ce qui rend les algorithmes naïfs inopérants.
On peut d'abord utiliser l'algorithme glouton pour obtenir une borne inférieure du max, disons k, mais on peut le faire aussi d'autres manières.
Il est très important de démarrer l'algorithme avec une telle borne k aussi haute que possible.
Cela dit on considère la relation d'inclusion entre parties.
A inclus dans B équivaut à A inter B = A équivaut encore au fait que le produit des fonctions caractéristiques de A et de B (qui se font par des opérations bitwise) est égal à la fonction caractéristique de A.
Voici deux évidences:
Si A est incus dans B, le poids de B est supérieur à celui de A
Si A est inclus dans B la valeur de B est supérieure à celle de A
Donc une partie déjà trop lourde ne peut contenir aucune solution. (nouvelle évidence)
Déterminons les 'descendants directs' d'une possibilité comme suit:
Les descendants directs de P s'obtiennent en ajoutant (si possible) à P un unique objet dont le poids est inférieur ou égal à l'objet le plus léger de P.
Donnons un exemple:
Les descendants directs de {0,1,0,0,0}
sont {0,1,1,0,0} , {0,1,0,1,0} {0,1,0,0,1}
On fait donc circuler l'unité sur la 'queue de zéros' de P pourvu que cette queue existe.
Cela dit les descendants de P sont définis récursivement comme étant soit leurs descendants directs, soit les descendants de ces descendants directs.
En particulier toute possibilité est incluse dans tous ses descendants (mais pas uniquement)
Tous les descendants de P={0,1,0,0,0} correspondent en fait à toutes les suites binaires de 3 éléments. Parmi celles-ci, il en est une de plus fort poids et de plus forte valeur dans notre cas c'est: {0,1,1,1,1}. Cette possibilité (de poids maximum) se détermine assez facilement à partir de P, et on peut calculer sa valeur Valmax. Si d'aventure cette valeur est inférieure à la borne k définie plus haut, cela signifie qu'il est impossible qu'aucune solution se trouve sur une branche issue de P.
Il y a donc deux raisons de ne pas développer une branche correspondant à une possibilité.
Soit P atteint déjà la poids maximal autorisé pour le sac.
Soit le Valmax de P est inférieur à la borne k. Dans ce cas on marque le nœud comme 'stérile'
On développe alors l'arbre 'en largeur'
Premier niveau:
Tous les descendants de {0,0,0,0,0}
soit 10000 01000 00100 00010 00001
On marque dans ce premier niveau tous les noeuds stériles
Puis on passe au niveau suivant en développant toutes les feuilles non stériles
Le processus s'arrête quand on n'obtient plus que des feuilles stériles. Il faut alors choisir celle qui a la plus grande valeur.
Cet algo se programme certainement assez facilement avec un LOO (C++, Java, C#).
Bien que cela puisse grandement faciliter la tâche du programmeur il n'est pas conseillé d'utiliser des structures de données dynamiques même quand le langage en fournit, car les temps d'accès sont élevés, et l'occupation mémoire importante.
Le début d'un code C++ pourrait donc ressembler à cela, mais il n'y a pas de petites économies si les poids restent modestes <256 , il ne faut pas hésiter à les déclarer en unsigned char, idem pour les valeurs
// implémentation de l'ensemble des possibles
class CPoss
{
// données partagées par toutes les instances
public:
static int objectsp[5]; // poids des objets en ordre dec
static int objectsv[5]; // valeurs des objets en ordre dec
private:
char fc[5]; // la fonction caractéristique sous forme d'une suite de 0 et de 1
int poids; // le poids
int valeur; // la valeur
int valmax; // valeur maximale de tous les descendants
public:
// constructeurs
// destructeur
// autres méthodes pour calculer poids valeur, valmax
};
// initialisation en dehors de la classe
int CPoss::objectsp[5]={12,4,2,1,1};
int CPoss::objectsv[5]={4,10,2,2,1};
// Noeuds pour la construction de l'arbre
// à partir de l'aîné les descendants d'un même parent forment une liste chaînée dans l'arbre
// ce qui facilite le parcours en largeur
class CNode
{CPoss P;
CNode * Children; // pointe vers la liste chaînée des enfants
CNode * Next; // pointe vers le frère suivant de moindre poids
bool sterile; // déterminé par une méthode spécialisée
public:
// constructeurs
// destructeur
// autres méthodes pour le marquage
};
class CTree
{
CNode * Root;// le père qui devra pointer sur un noeud contenant la CPoss "00000"
public:
// constructeurs
// destructeur
// autres méthodes pour le développement et la recherche
}; |
