Tableau 2D / Maximum de cases / 1 par axe

[JeanLouis69]

Bonsoir !

Ceci est une bouteille à la mer

Mon Bac S et mes 8 ans de prog ne m'ont pas suffit pour trouver solution à mon problème, facile en apparence..

Voici plusieurs tableaux :
https://drive.google.com/file/d/1YIco-h ... sp=sharing

Pour chaque tableau, je désigne de manière arbitraire des cases vertes, et cherche à calculer le nombre de cases violettes, pour Violets = l'ensemble des cases violettes telles que :
- elles sont vertes à la base
- il n'y ait qu'une seule case violette par axe (x, y)
- il y a ait le plus de cases violettes

Je n'arrive juste pas à me représenter cela de manière mathématique, mais vraiment, vraiment pas du tout

Quelqu'un aurait plus de hauteur que moi ?

Merci !

[fatal_error]

slt,

Tu peux faire de la PLNE

chaque case est un booléen, je les nommes x_ij
tu rajoutes des contraintes pour les lignes et les colonnes
somme_sur_i des x_ij <= 1
somme_sur_j des x_ij <= 1
et tu veux maximiser somme x_ij
(du coup tu mets la condition que tout x_ij est 0 <= x_ij <= 1)

sans sortir l'artillerie lourde (certains repliqueront que c'est relatif ^^'), tu peux aussi y aller bourrin via prog dynamique


tu peux remarquer que pour une grille

Code: Tout sélectionner

V.V
V.V


si tu choisis ces deux cases

Code: Tout sélectionner

X00
00X


ou ces deux cases

Code: Tout sélectionner

..X
X..


alors c'est identique (car les lignes/colonnes "condamnées" sont les même)
du coup tu peux eviter lexploration de la branche si tu as déjà une configuration "identique"

Code: Tout sélectionner

const data = `
..V..V.
V..V..V
.V..V..
..V..V.
V..V..V
.V..V..
..V..V.
`
const b = data.trim().split('\n').map((x, i) => x.trim().split('').map((x, j)=> x=='V' && ({i,j})))


const getBiggest = m => {
  let bestLength = 0
  let best = []
  for (let v of m.values()) {
    if (v.length > bestLength) {
      bestLength = v.length
      best = v
    }
  }
  return best
}
// the first element is a string representing the consumed (vertical|horizontal)lines
// encoded as lineIds:columnIds where lineIds and columnIds are bitmask
// second element is an array of taken Vs
const IDENTITY = ['0:0', []]
let m = new Map([IDENTITY])
let next
let best = null
for (const x of b.flatMap(y => y)) {
  if (!x) continue // not a V
  next = new Map(m.entries())
  for (const [key, values] of m) {
    const [lineId, columnId] = key.split(':').map(x => parseInt(x, 10))
    // intersection
    if ((2**x.i & lineId) !== 0 || (2**x.j & columnId) !== 0) {
      continue
    }

    const hash = [lineId | 2**x.i, columnId | 2**x.j].join(':')
    next.set(hash, values.concat(x))
  }

  m = next
}


const newBoard = b.slice(0).map(x => x.slice(0).map(x => typeof(x) === 'object' ? 'V' : '.'))
getBiggest(m).forEach(({i, j})=> newBoard[i][j] = 'X')

console.log(data)
console.log(newBoard.map(x => x.join('')).join('\n'))
// affiche
/*
..V..V.
V..V..V
.V..V..
..V..V.
V..V..V
.V..V..
..V..V.

..X..V.
X..V..V
.X..V..
..V..X.
V..X..V
.V..X..
..V..V.

*/


https://jsfiddle.net/7pvLfnem/1/