On se retrouve aujourd'hui pour la solution du précédent #KataOfTheWeek proposé par Josquin en début de semaine !
private static int getMinimumCodeSmellsGap(Map<Integer, Integer> enemies, List<Integer> weights) {
int halfNumberOfWeight = weights.stream().mapToInt(x -> x).sum() / 2;
// L(i, j) <-> if it is possible to have a side with weight j, considering
// only the developers in the first i couples of enemies
boolean[][] L = new boolean[enemies.size() + 1][halfNumberOfWeight + 1];
// initialize to false
for (int i = 0; i <= enemies.size(); i++) {
for (int j = 0; j <= halfNumberOfWeight; j++) {
L[i][j] = false;
}
}
// L(0, 0) = true
// L(0, j) = false for j != 0
L[0][0] = true;
// L(i+1, j) = L(i, j-w[k]) or L(i, j), where k is one of the developers
// concerned by the (i+1)-th enemy
int jWeight = 0; // How many enemies have been explored
for (Map.Entry<Integer, Integer> rivalry : enemies.entrySet()) {
for (int j = 0; j <= halfNumberOfWeight; j++) {
if (rivalry.getValue() != -1) {
if (j - weights.get(rivalry.getKey()) >= 0) {
L[jWeight + 1][j] = L[jWeight][j - weights.get(rivalry.getKey())]
|| L[jWeight + 1][j];
}
if (j - weights.get(rivalry.getValue()) >= 0) {
L[jWeight + 1][j] = L[jWeight][j - weights.get(rivalry.getValue())]
|| L[jWeight + 1][j];
}
} else {
if (j - weights.get(rivalry.getKey()) >= 0) {
L[jWeight + 1][j] = L[jWeight][j - weights.get(rivalry.getKey())]
|| L[jWeight][j];
} else
L[jWeight + 1][j] = L[jWeight][j];
}
}
jWeight++;
}
int maxNumberOfWeight = halfNumberOfWeight;
while ((maxNumberOfWeight >= 0) && (!L[enemies.size()][maxNumberOfWeight])) {
maxNumberOfWeight--;
}
return 2 * (halfNumberOfWeight - maxNumberOfWeight);
}
A bientôt pour un nouveau #KataOfTheWeek !