Pourquoi l'algorithme de changement de pièces par gourmandise ne fonctionne-t-il pas pour certains jeux de pièces ?

Question

Je comprends comment fonctionne l'algorithme gourmand pour le problème du changement de pièces (payer un montant spécifique avec le plus petit nombre possible de pièces) - il sélectionne toujours la pièce dont la dénomination est la plus grande et qui ne dépasse pas la somme restante - et qu'il trouve toujours la solution correcte pour des ensembles de pièces spécifiques.

Mais pour certains ensembles de pièces, il existe des sommes pour lesquelles l'algorithme gourmand échoue. Par exemple, pour l'ensemble {1, 15, 25} et la somme 30, l'algorithme gourmand choisit d'abord 25, laissant un reste de 5, puis cinq 1 pour un total de six pièces. Mais la solution avec le nombre minimal de pièces est de choisir deux fois 15.

Quelles conditions un ensemble de pièces doit-il remplir pour que l'algorithme glouton trouve la solution minimale pour toutes les sommes ?

Answer 1

La théorie :

Si l'algorithme greedy produit toujours une réponse optimale pour un ensemble donné de pièces, on dit que cet ensemble est canonique .

Déclarer le le meilleur test algorithmique connu [O(n^3)] pour déterminer si un ensemble arbitraire de n pièces est canonique aussi succinctement que possible :

[c1,c2,..cn] is canonical iff for all w_ij |G(w_ij)| = |M(w_ij)|, 1 < i <= j <= n 

où [c1,c2,...cn] est la liste des dénominations de pièces triées par ordre décroissant avec cn = 1

G(x) représente le résultat du vecteur de pièces de l'exécution de l'algorithme greedy sur l'entrée x (retourné comme [a1, a2,..., an] où ai est le nombre de ci )

M(x) représente une représentation vectorielle de la pièce de monnaie x qui utilise le moins de pièces

|V| représente la taille du vecteur pièce V : le nombre total de pièces dans le vecteur

et w_ij est la valeur évaluée du vecteur pièce produit par G(c_(i-1) - 1) après avoir incrémenté son j par 1 et en mettant à zéro tous ses comptes de pièces à partir de j+1 a n .

Mise en œuvre (JavaScript) :

/**
 * Check if coins can be used greedily to optimally solve change-making problem
 * coins: [c1, c2, c3...] : sorted descending with cn = 1
 * return: [optimal?, minimalCounterExample | null, greedySubOptimal | null] */
function greedyIsOptimal(coins) {
  for (let i = 1; i < coins.length; i++) {
    greedyVector = makeChangeGreedy(coins, coins[i - 1] - 1)
    for (let j = i; j < coins.length; j++) {
      let [minimalCoins, w_ij] = getMinimalCoins(coins, j, greedyVector)
      let greedyCoins = makeChangeGreedy(coins, w_ij)
      if (coinCount(minimalCoins) < coinCount(greedyCoins))
        return [false, minimalCoins, greedyCoins]
    }
  }
  return [true, null, null]
}

// coins [c1, c2, c3...] sorted descending with cn = 1 => greedy coinVector for amount
function makeChangeGreedy(coins, amount) {
  return coins.map(c => {
    let numCoins = Math.floor(amount / c);
    amount %= c
    return numCoins;
  })
}
// generate a potential counter-example in terms of its coinVector and total amount of change
function getMinimalCoins(coins, j, greedyVector) {
  minimalCoins = greedyVector.slice();
  minimalCoins[j - 1] += 1
  for (let k = j; k < coins.length; k++) minimalCoins[k] = 0
  return [minimalCoins, evaluateCoinVector(coins, minimalCoins)]
}
// return the total amount of change for coinVector
const evaluateCoinVector = (coins, coinVector) =>
  coins.reduce((change, c, i) => change + c * coinVector[i], 0)

// return number of coins in coinVector
const coinCount = (coinVector) =>
  coinVector.reduce((count, a) => count + a, 0)

/* Testing */
let someFailed = false;
function test(coins, expect) {
  console.log(`testing ${coins}`)
  let [optimal, minimal, greedy] = greedyIsOptimal(coins)
  if (optimal != expect) (someFailed = true) && console.error(`expected optimal=${expect}
  optimal: ${optimal}, amt:${evaluateCoinVector(coins, minimal)}, min: ${minimal}, greedy: ${greedy}`)
}
// canonical examples
test([25, 10, 5, 1], true) // USA
test([240, 60, 24, 12, 6, 3, 1], true) // Pound Sterling - 30
test([240, 60, 30, 12, 6, 3, 1], true) // Pound Sterling - 24
test([16, 8, 4, 2, 1], true) // Powers of 2
test([5, 3, 1], true) // Simple case

// non-canonical examples
test([240, 60, 30, 24, 12, 6, 3, 1], false) // Pound Sterling
test([25, 12, 10, 5, 1], false) // USA + 12c
test([25, 10, 1], false) // USA - nickel
test([4, 3, 1], false) // Simple cases
test([6, 5, 1], false)

console.log(someFailed ? "test(s) failed" : "All tests passed.")

Answer 2

Aujourd'hui, j'ai résolu une question similaire à celle-ci sur Codeforces (le lien sera fourni à la fin). Ma conclusion est que pour que le problème de la monnaie soit résolu par l'algorithme de Greedy, il doit satisfaire la condition suivante:-

Lors du tri des valeurs des pièces par ordre croissant, toutes les valeurs supérieures à l'élément actuel doivent être divisibles par l'élément actuel.

Par exemple, pièces = {1, 5, 10, 20, 100}, ce qui donnera une réponse correcte puisque {5,10, 20, 100} sont toutes divisibles par 1,{10,20, 100} sont toutes divisibles par 5,{20,100} sont toutes divisibles par 10,{100} sont toutes divisibles par 20.

J'espère que cela vous donnera une idée.

996 A - Toucher la loterie https://codeforces.com/blog/entry/60217

Answer 3

Un cas facile à retenir est que tout ensemble de pièces de monnaie tel que, si elles sont triées par ordre croissant et que vous avez :

coin[0] = 1
coin[i+1] >= 2 * coin[i], for all i = 0 .. N-1 in coin[N]

Alors un algorithme gourmand utilisant de telles pièces fonctionnera.

En fonction de la plage que vous interrogez, il peut y avoir une répartition plus optimale (en termes de nombre de pièces requises). Par exemple, si vous considérez la plage (6..8) et que vous avez les pièces <6, 7, 8> au lieu de <1, 2, 4, 8>.

L'allocation la plus efficace de pièces de monnaie qui est complète sur N+ est à l'égalité de l'ensemble des règles ci-dessus, vous donnant les pièces 1, 2, 4, 8 ... ; qui est simplement la représentation binaire de n'importe quel nombre. Dans un certain sens, la conversation entre les bases est un algorithme gourmand en soi.

Une preuve de l'inégalité >= 2N est fournie par Max Rabkin dans cette discussion : http://olympiad.cs.uct.ac.za/old/camp0_2008/day1_camp0_2008_discussions.pdf