[1] | 1 | #include <stdio.h> |
---|
| 2 | |
---|
| 3 | #include "heure.h" |
---|
| 4 | |
---|
| 5 | static int N; |
---|
| 6 | static heure* valeur; |
---|
| 7 | static bool* ok; |
---|
| 8 | static bool* solution; |
---|
| 9 | static heure seuil; |
---|
| 10 | static heure grand_total; |
---|
| 11 | |
---|
| 12 | //------------------------------------------------------ |
---|
| 13 | void permutations (int valeurs, int possibilites, int pos = 0) |
---|
| 14 | //------------------------------------------------------ |
---|
| 15 | { |
---|
| 16 | if (valeurs <= 0) |
---|
| 17 | { |
---|
| 18 | // c'est la fin |
---|
| 19 | heure total; |
---|
| 20 | int k; |
---|
| 21 | |
---|
| 22 | // On calcule le total des valeurs marquees |
---|
| 23 | |
---|
| 24 | for (k = 0; k < N; k++) |
---|
| 25 | { |
---|
| 26 | if (ok[k]) total += valeur[k]; |
---|
| 27 | } |
---|
| 28 | |
---|
| 29 | if (total <= seuil) |
---|
| 30 | { |
---|
| 31 | if (total > grand_total) |
---|
| 32 | { |
---|
| 33 | // nouveau total |
---|
| 34 | grand_total = total; |
---|
| 35 | |
---|
| 36 | for (k = 0; k < N; k++) |
---|
| 37 | { |
---|
| 38 | solution[k] = ok[k]; |
---|
| 39 | } |
---|
| 40 | } |
---|
| 41 | else |
---|
| 42 | { |
---|
| 43 | // pas mieux |
---|
| 44 | } |
---|
| 45 | } |
---|
| 46 | else |
---|
| 47 | { |
---|
| 48 | // trop grand |
---|
| 49 | } |
---|
| 50 | |
---|
| 51 | return; |
---|
| 52 | } |
---|
| 53 | |
---|
| 54 | // Protection : ca ne devrait jamais arriver !!! |
---|
| 55 | if (valeurs > possibilites) return; |
---|
| 56 | |
---|
| 57 | // On essaie en utilisant la première case |
---|
| 58 | ok[pos] = true; |
---|
| 59 | permutations (valeurs-1, possibilites-1, pos+1); |
---|
| 60 | |
---|
| 61 | // On essaie en n'utilisant pas la première case |
---|
| 62 | ok[pos] = false; |
---|
| 63 | permutations (valeurs, possibilites-1, pos+1); |
---|
| 64 | } |
---|
| 65 | |
---|
| 66 | //------------------------------------------------------ |
---|
| 67 | int main (int argc, char* argv[]) |
---|
| 68 | //------------------------------------------------------ |
---|
| 69 | { |
---|
| 70 | // Recuperation des parametres |
---|
| 71 | // |
---|
| 72 | // Le premier est le seuil |
---|
| 73 | argc--; |
---|
| 74 | argv++; |
---|
| 75 | |
---|
| 76 | seuil = argv[0]; |
---|
| 77 | |
---|
| 78 | // Ensuite on a N valeurs |
---|
| 79 | argc--; |
---|
| 80 | argv++; |
---|
| 81 | |
---|
| 82 | N = argc; |
---|
| 83 | |
---|
| 84 | valeur = new heure[N]; |
---|
| 85 | |
---|
| 86 | int k; |
---|
| 87 | |
---|
| 88 | for (k = 0; k < N; k++) |
---|
| 89 | { |
---|
| 90 | valeur[k] = argv[0]; |
---|
| 91 | argc--; |
---|
| 92 | argv++; |
---|
| 93 | } |
---|
| 94 | |
---|
| 95 | // On a besoin de N etats pour cocher les valeurs. |
---|
| 96 | // Et d'une copie pour la solution. |
---|
| 97 | ok = new bool[N]; |
---|
| 98 | solution = new bool[N]; |
---|
| 99 | |
---|
| 100 | // On essaie les permutations successivement pour |
---|
| 101 | // des nombres de valeurs de + en + grands parmi N |
---|
| 102 | for (k = 1; k <= N; k++) |
---|
| 103 | { |
---|
| 104 | permutations (k, N); |
---|
| 105 | } |
---|
| 106 | |
---|
| 107 | for (k = 0; k < N; k++) |
---|
| 108 | { |
---|
| 109 | valeur[k].print (); |
---|
| 110 | if (solution[k]) printf (" <--- "); |
---|
| 111 | printf ("\n"); |
---|
| 112 | } |
---|
| 113 | printf ("-----\n"); |
---|
| 114 | grand_total.print (); |
---|
| 115 | printf ("\n"); |
---|
| 116 | |
---|
| 117 | return (0); |
---|
| 118 | } |
---|
| 119 | |
---|