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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class Mine implements Comparable<Mine> {
public long cout;
public long production;
public String nom;
public Mine(long cout, long production, String nom) {
this.cout = cout;
this.production = production;
this.nom = nom;
}
public Mine() {
}
public int compareTo(Mine o) {
long diffc = this.cout - o.cout;
if (diffc > 0) {
return 1;
} else if (diffc < 0) {
return -1;
} else {
long diffp = this.production - o.production;
if (diffp < 0) {
return -1;
} else if (diffp > 0) {
return 1;
} else {
return 0;
}
}
}
/*
* Type de retour de la fonction de calcul : un temps total et l'ordre de
* construction des mines
*/
public class Res {
public long temps;
public List<Mine> mines;
public Res(long temps, List<Mine> mines) {
this.temps = temps;
this.mines = mines;
}
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Mine m1 = new Mine(10, 4, "m1");
Mine m2 = new Mine(5, 3, "m2");
Mine m3 = new Mine(1, 1, "m3");
List<Mine> mines = new LinkedList<Mine>();
mines.add(m1);
mines.add(m2);
mines.add(m3);
mines.add(m1);
mines.add(m1);
mines.add(m3);
// Tri pour optimisation des permutations
Collections.sort(mines);
List<Mine> minesConstruites = new LinkedList<Mine>();
Res res = (new Mine()).computeTime(mines, 1L, 0L, 0L, minesConstruites);
System.out.println(res.temps);
for (Mine mine : res.mines) {
System.out.print(mine.nom + " | ");
}
System.out.println();
}
/*
* Fonction de calcul du temps et de l'ordre de construction
*/
public Res computeTime(List<Mine> minesRestantes, long production,
long argent, long temps, List<Mine> minesConstruites) {
if (minesRestantes.isEmpty()) {
return (new Res(temps, minesConstruites));
}
List<Res> resMin = new ArrayList<Res>(minesRestantes.size());
Mine derniereMine = minesRestantes.get(0);
// Pour chaque mine restante, on calcule le meilleur temps si elle est
// la prochaine construite
for (int index = 0; index < minesRestantes.size(); ++index) {
List<Mine> minesRestantes_ = new LinkedList<Mine>(minesRestantes);
Mine mineCour = minesRestantes_.remove(index);
// Si la mine courante est la meme que la precedente, inutile de
// recalculer le cout de la construire
if (index > 0 && mineCour.compareTo(derniereMine) == 0) {
continue;
}
List<Mine> minesConstruites_ = new LinkedList<Mine>(minesConstruites);
// On ajoute la mine a construire dans la liste des mines construites
minesConstruites_.add(mineCour);
// On peut la construire directement
if (mineCour.cout <= argent) {
resMin.add(computeTime(minesRestantes_,
production + mineCour.production,
argent - mineCour.cout,
temps,
minesConstruites_));
} // On n'a pas assez d'argent, on calcule le temps d'attente
// necessaire pour engager la construction
else {
long difference = mineCour.cout - argent;
long modulo = difference % production;
short offset = 0;
if (modulo != 0) {
offset = 1;
}
long temps_construction = (difference / production) + offset;
resMin.add(computeTime(minesRestantes_,
production + mineCour.production,
argent + (temps_construction * production) - mineCour.cout,
temps + temps_construction,
minesConstruites_));
}
// On met a jout la derniere mine construite
derniereMine = mineCour;
}
// On retourne le resultat ayant un temps minimum
int indexMin = 0;
long tempsMinGlob = Long.MAX_VALUE;
for (int index = 0; index < resMin.size(); ++index) {
if (resMin.get(index).temps < tempsMinGlob) {
tempsMinGlob = resMin.get(index).temps;
indexMin = index;
}
}
return resMin.get(indexMin);
}
} |
Ordre de construction de mines
Répondre avec citation
Partager