L' algorithme du caissier est un algorithme permettant de modifier le nombre minimal de pièces qui fonctionne assez bien pour la plupart des systèmes monétaires. Cependant, comme la plupart des algorithmes gloutons, il n’est pas dépourvu de défauts. Si un système de devise est configuré correctement (ou tout simplement faux), il existe certaines valeurs pour lesquelles l'algorithme du caissier ne trouvera pas le changement optimal.

Prenons l'exemple suivant:

Nous avons des pièces de 4 ¢, 3 ¢ et 1 ¢. Nous voulons faire 6 ¢.

L'algorithme du caissier choisira d'abord autant de pièces parmi les plus grosses pièces (un 4 ¢ pour commencer), puis soustraira et répétera. Cela donnera une pièce de 4 ¢ et deux pièces de 1 ¢, pour un total de 3 pièces.

Malheureusement pour l'algorithme, il existe un moyen de faire 6 ¢ avec seulement deux pièces (deux pièces de 3 ¢).

Un système de changement sera considéré canonique ssi pour toutes les valeurs entières, l'algorithme du caissier trouvera le nombre optimal de pièces.

Tâche

Votre tâche consistera à prendre un système soit en tant que conteneur non ordonné, soit en conteneur ordonné trié et ordonné représentant des valeurs de pièces et en générant une valeur de vérité si l’entrée du système est canonique et falsy sinon.

Votre programme devrait fonctionner pour tous les systèmes pouvant créer n'importe quelle valeur. (c’est-à-dire que tous les systèmes auront une pièce de 1 ¢)

C'est le code de golf le moins d'octets gagne.

Cas de test

Cette liste n’est nullement exhaustive, votre programme devrait fonctionner pour toutes les entrées valides.

1, 3, 4       -> 0
1, 5, 10, 25  -> 1
1, 6, 10, 25  -> 0
1, 2, 3       -> 1
1, 8, 17, 30  -> 0
1, 3, 8, 12   -> 0
1, 2, 8, 13   -> 0
1, 2, 4, 6, 8 -> 1

Haskell, 94 87 82 octets

f s=and[j i-2<j(i-x)|let j i=last$0:[1+j(i-x)|x<-s,x<i],i<-[1..2*last s],x<-s,x<i]

Cette solution définit une fonction jqui exécute l'algorithme du caissier et nous indique le nombre de pièces utilisées par le caissier. nous vérifions ensuite jusqu'à deux fois le plus grand nombre de la liste, en supposant que le système a été canonique pour tous les numéros précédents, que prendre la plus grosse pièce possible est le bon choix.

cette solution suppose que l'entrée est triée.

vérifier qu'il est suffisant de vérifier jusqu'à deux fois le plus grand nombre: supposons que le système ne soit pas canonique pour un certain nombre i, et que kle plus grand nombre de la liste ne soit pas supérieur à i. supposons que i >= 2ket que le système soit canonique pour tous les nombres inférieurs à i.

prenez un moyen optimal de fabriquer ides pièces de monnaie et supposez qu’elles ne contiennent pas la pièce de monnaie k. si nous jetons l'une des pièces, la nouvelle somme de pièces doit être supérieure ket inférieure à i- mais l'algorithme du caissier sur ce nombre utilisera la kpièce - et par conséquent, cet ensemble de pièces peut être remplacé par un ensemble égal de pièces. contenant la pièce k, il existe donc un ensemble de pièces contenant la pièce kpour le nombre iet, par induction, l’algorithme du caissier renvoie le choix optimal.

Cet argument montre vraiment que nous devons seulement vérifier jusqu'à la somme des deux plus gros éléments - mais c'est plus long à faire.

Edit: cinq octets de moins grâce à Ørjan Johansen!

Pyth, 18 à 15 octets

!x#eST.gsky_S*e

Suite de tests

Une autre sorte de force brute. Cela commence par former toutes les collections de pièces avec un maximum de k, où k est la plus grande pièce, supposée être la dernière. Je crois que cela suffit toujours pour former deux jeux de pièces avec la même somme, un gourmand et un plus court, chaque fois qu'une telle paire existe.

Je localise alors une telle paire comme suit:

Les sous-ensembles sont générés par ordre de taille croissante et lexicographiquement par position dans l’entrée. Groupez les collections de pièces de monnaie par leurs sommes, de manière stable. Chaque collection de pièces étant générée par ordre décroissant, la solution gourmande sera le premier élément du groupe si et seulement si la solution gourmande est optimale et ce sera le dernier élément du groupe lexicographiquement. Ainsi, nous trouvons la solution gloutonne et filtrons sur un index non nul dans le groupe. Si le jeu de pièces est canonique, cela filtrera tout. Nous nions donc logiquement le résultat et la sortie.

Explication:

!x#eST.gsky_S*e
!x#eST.gsky_S*eQQ   Variable introduction.
                    Q = eval(input()) - sorted list of coins.
              eQ    Greatest coin in the list
             *  Q   Repeat that many times.
            S       Sort the coins
           _        Reverse, so we have the coins in descending order.
          y         Form all subsets, in increasing size then
                    decreasing lexicographic order.
      .gsk          Group by sum
 x#                 Filter by the index in the group of
   eST              The last element lexicographically (greedy solution).
!                   Logically negate.

PHP, 323 octets

De la même manière que les autres comptent les pièces jusqu’à la somme des deux derniers éléments du tableau

<?function t($g){rsort($g);$m=array_slice($g,1);for($y=1,$i=$g[0];$i<$g[0]+$m[0];$i++){$a=$b=$i;$p=0;$r=$s=[];while($a||$b){$o=$n=0;$g[$p]<=$a?$a-=$r[]=$g[$p]:$o=1;($m[$p]??1)<=$b?$b-=$s[]=$m[$p]:$n=1;$p+=$o*$n;}$y*=count($r)<=count($s);}return$y;}for($i=0,$t=1;++$i<count($a=$_GET[a]);)$t*=t(array_slice($a,0,$i+1));echo$t;

Ma meilleure et la plus longue réponse, je crois> 370 octets

Je ne donne qu'une version développée car il est plus long que ma réponse avant

for($x=1,$n=0,$f=[];++$n<count($a)-1;){
$z=array_slice($a,0,$n+1);
$q=$a[$n]-$a[$n-1];
$i=array_fill(1,$c=max($a[$n+1]??1,11),"X");#$q*$a[$n]
$f=range($a[$n],$c,$q);

$f[]=2*$a[$n];
for($d=[$z[$n]],$j=0;$j<$n;){
   $f[]=$a[$n]+$d[]=$z[$n]-$z[$j++]; 
}

while($f){
    $i[$t=array_pop($f)]="T";
    foreach($d as $g)
    if(($l=$t+$g)<=$c)$f[]=$l;
}

foreach($i as$k=>$v){
    if(in_array($k,$z))$i[$k]="S";
}
#var_dump($i);
if($i[$a[$n+1]]=="X")$x*=0;
}
echo$x;

Explication de cette réponse

Version en ligne

1. Définissez all dans le tableau sur false == X

2. Définissez tous les nombres du tableau que vous contrôlez sur S

3. Différences constatées entre le dernier S et l'autre S ou 0

4. Commence en dernier S dans le tableau

5. Définissez tous les nombres sur D Où Dernier S + une de toutes les différences

6. Commencez à tous D

7. SET "T" à D valeurs dans le tableau

8. GOTO 5 Répétez l'opération avec tous les DI trouvés ne l'ont pas fait dans le code

9. Si l'élément suivant du tableau contient X, il s'agit d'un faux cas, sinon, True

Étapes supplémentaires La différence est dans le cas dans l'extrait 3 Entre 1 et 4 sont 2 X Cela signifie que vous avez besoin du deuxième D d'ici l'étape 5. Après cette valeur dans ce cas, 10 sont tous les cas vrais, j'ai pu voir jusqu'à présent qu'il existe une relation entre la différence et le nombre dans le tableau que vous contrôlez pour calculer combien de D (Étape 5) vous devez obtenir le point avant de trouver le dernier faux cas.

Vous définissez plusieurs valeurs du dernier élément directement sur true. Ces points peuvent faire la différence pour décider s’il est possible que le nombre de pièces gloutonnes avec la valeur suivante soit identique au multiple du dernier dans le tableau. D'autre part, vous pouvez définir l'ennemi

1. Définir le premier ennemi à 1 + dernier S

2. A partir de ce point, ajoutez chaque valeur dans le tableau pour définir les prochains ennemis.

3. Commence avec le dernier ennemi Goto 2

Si vous avez maintenant des ennemis et des cas réels, la probabilité que les comptes soient identiques est de plus en plus grande. Avec plus de D, la probabilité diminue.

table{width:80%}
td,th{width:45%;border:1px solid blue;}

<table>
  <caption>Working [1,4]</caption>
<tr><th>Number</th><th>Status</th></tr>
<tr><td>1</td><td>S</td></tr>
<tr><td>2</td><td>X</td></tr>
<tr><td>3</td><td>X</td></tr>
<tr><td>4</td><td>S</td></tr>
<tr><td>5</td><td>X</td></tr>
<tr><td>6</td><td>X</td></tr>
<tr><td>7</td><td>D3</td></tr>
<tr><td>8</td><td>D4</td></tr>
<tr><td>9</td><td>X</td></tr>
<tr><td>10</td><td>D3D3</td></tr>
<tr><td>11</td><td>D4D3</td></tr>
<tr><td>12</td><td>D4D4</td></tr>
<tr><td>13</td><td>D3D3D3</td></tr>
<tr><td>14</td><td>D4D3D3</td></tr>
<tr><td>15</td><td>D4D4D4</td></tr>
<tr><td>16</td><td>D4D4D3</td></tr>
</table>
<ul>
  <li>S Number in Array</li>
  <li>D Start|End point TRUE sum Differences from last S</li>
  <li>X False</li>
  </ul>

plus? Bytes Merci @JonathanAllan de me donner un cas de test erroné
262 octets Presque mais pas assez bon 4 mauvais test du moment

cas de test [1,16,256] avant devrait être vrai après faux

<?for($q=[1],$i=0,$t=1,$w=[0,1];++$i<count($a=$_GET[v]);$w[]=$a[$i],$q[]=$m)($x=$a[$i]-$a[$i-1])>=($y=$a[$i-1]-$a[$i-2])&&((($x)%2)==(($m=(($a[$i]+$x)*$a[$i-1])%$a[$i])%2)&&$m>array_sum($q)||(($x)%2)==0&&(($a[$i]-$a[$i-2])*2%$y)==0||in_array($m,$w))?:$t=0;echo$t;

Ordre croissant du tableau

Explication

for($q=[1],$i=0,$t=1,$w=[0,1] # $t true case $q array for modulos $w checke values in the array
;++$i<count($a=$_GET[v])   #before loop
;$w[]=$a[$i],$q[]=$m) # after loop $q get the modulo from the result and fill $w with the checked value

($x=$a[$i]-$a[$i-1])>=($y=$a[$i-1]-$a[$i-2]) 
# First condition difference between $a[i] and $a[$i-1] is greater or equal $a[$i-1] and $a[$i-2]
# if $a[$-1] == 1 $a[$i-2] will be interpreted as 0
&&  ## AND Operator with the second condition
(
(($x)%2)==   # See if the difference is even or odd
(($m=(($a[$i]+$x)*$a[$i-1])%$a[$i])%2)&&$m>array_sum($q)
# After that we multiply the result with the lower value *$a[$i-1]
    # for this result we calculate the modulo of the result with the greater value %$a[$i]
    # if the difference and the modulo are both even or odd this belongs to true
# and the modulo of the result must be greater as the sum of these before
    # Ask me not why I have make try and error in an excel sheet till I see this relation
||
(($x)%2)==0&&(($a[$i]-$a[$i-2])*2%$y)==0 # or differce modulator is even and difference $a[$i],$a[$i-1] is a multiple of half difference $a[$i-1],$a[$i-2] 
||
in_array($m,$w) # if the modulo result is equal to the values that we have check till this moment in the array we can also neglect the comparison
)
?:$t=0; # other cases belongs to false
echo$t; #Output

Il semble que ce que j'ai vu dans le tableau contienne les valeurs de [1,2,3,4,5,6] et que je ne modifie que le dernier élément jusqu'à 9. Pour 2to3 et 4to5, nous créons la valeur de la valeur la plus basse dans le champ. calcul modulo

table{width:95%;}th,td{border:1px solid}

<table><tr><th>difference</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><th>difference modulo 2</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><th>value</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td></tr>
<tr><th>result</th><td></td><td>3</td><td>8</td><td>15</td><td>24</td><td>35</td></tr>
<tr><th>modulo value great</th><td></td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td></tr>
<tr><th>modulo 2</th><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr>
<tr><th></th><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><th>difference</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>2</td></tr>
<tr><th>difference modulo 2</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td></tr>
<tr><th>value</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>7</td></tr>
<tr><th>result</th><td></td><td>3</td><td>8</td><td>15</td><td>24</td><td>45</td></tr>
<tr><th>modulo value great</th><td></td><td>1</td><td>2</td><td>3</td><td>4</td><td>3</td></tr>
<tr><th>modulo 2</th><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr>
<tr><th></th><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><th>difference</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>3</td></tr>
<tr><th>difference modulo 2</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><th>value</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>8</td></tr>
<tr><th>result</th><td></td><td>3</td><td>8</td><td>15</td><td>24</td><td>55</td></tr>
<tr><th>modulo value great</th><td></td><td>1</td><td>2</td><td>3</td><td>4</td><td>7</td></tr>
<tr><th>modulo 2</th><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td></tr>
<tr><th></th><td></td><td></td><td></td><td></td><td></td><td></td></tr>
<tr><th>difference</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>4</td></tr>
<tr><th>difference modulo 2</th><td></td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td></tr>
<tr><th>value</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>9</td></tr>
<tr><th>result</th><td></td><td>3</td><td>8</td><td>15</td><td>24</td><td>65</td></tr>
<tr><th>modulo value great</th><td></td><td>1</td><td>2</td><td>3</td><td>4</td><td>2</td></tr>
<tr><th>modulo 2</th><td></td><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td></tr></table>

JavaScript (ES6), 116 125 130

l=>eval("r=(d,k)=>d?--k&&l.map(v=>v>d||r(d-v,k)):x=1;for(x=l[0]*2;--x>1;r(x,g))g=0,h=x,l.map(v=>(g+=h/v|0,h%=v));x")

Cela nécessite que le tableau en entrée soit trié par ordre décroissant. Pour chaque valeur comprise entre 2N et 2 (N étant la valeur de pièce maximale), il recherche le nombre de pièces de l'algorithme glouton et tente de trouver un ensemble de pièces plus petit.

Moins golfé

l=>{
  // recursive function to to find a smaller set of coins
  // parameter k is the max coin limit
  r = (d,k) => d // check if difference is not 0
     ? --k // if not, and if the number of coins used will be less than limit
      && l.map(v => v>d || r(d-v, k))  // proceed with the recursive search
     : x=1 // if diff is 0, value found, set x to 1 to stop the loop
  for( x=l[0]*2; --x > 1; )  
    g=0, h=x, l.map(v=>(g += h/v|0, h %= v)), // find g with the greedy algorithm
    r(x,g) // call with initial difference equal to target value
  return x
}

Tester

f=
l=>eval("r=(d,k)=>d?--k&&l.map(v=>v>d||r(d-v,k)):x=1;for(x=l[0]*2;--x>1;r(x,g))g=0,h=x,l.map(v=>(g+=h/v|0,h%=v));x")

/* No eval
f=l=>{
  r=(d,k)=>d?--k&&l.map(v=>v>d||r(d-v,k)):x=1;
  for(x=l[0]*2;--x>1;r(x,g))
    g=0,h=x,l.map(v=>(g+=h/v|0,h%=v));
  return x;
}*/

;[
 [[100,50,20,10,5,2,1],1], [[4,3,1],0],
 [[25,10,5,1],1], [[25,10,6,1],0],
 [[3,2,1],1], [[30,17,8,1], 0], 
 [[12,8,3,1],0], [[13,8,2,1], 0]
].forEach(t=>{
  var i=t[0],k=t[1],r=f(i),
      msg=((r==k)?'OK ':'KO ')+i+' -> '+r
      + (r==k?'':' (should be '+k+')')
  O.textContent += msg+'\n'
})

function test()
{
  var i=I.value.match(/\d+/g).map(x=>+x).sort((a,b)=>b-a)
  O.textContent = i+' -> '+f(i)+'\n'+O.textContent
 }

#I { width:50% }

<input id=I value='1 4 9'><button onclick='test()'>test</button>
<pre id=O></pre>

Python, 218 211 205 octets

-1 octet grâce à @TuukkaX (un espace peut être supprimé entre <3et or)

from itertools import*
g=lambda x,c,n=0:x and g(x-[v for v in c if v<=x][0],c,n+1)or n
lambda c:len(c)<3or 1-any(any(any(x==sum(p)for p in combinations(c*i,i))for i in range(g(x,c)))for x in range(c[0]*2))

repl.it

Entrer dans l'ordre décroissant.

Force brute horriblement. N'importe quel ensemble d'une pièce unique et d'une autre pièce est canonique. Pour les plus grandes séries, le plus petit des cas d'échec, s'il en existe une, sera supérieur ou égal à la 3ème plus petite pièce (je ne suis pas sûr de savoir comment il pourrait être égal!) Et inférieur à la somme des deux plus grandes pièces - voir le présent document (qui référence une autre mais donne également une méthode O (n ^ 3)).

g compte les pièces utilisées par la méthode gourmande, et la fonction non nommée parcourt les candidats possibles (en réalité de 0 à une fois moins que le double de la plus grosse pièce pour enregistrer des octets) et recherche toute collection de moins de pièces équivalant à ce montant.

gfonctionne en effectuant ce qu'un caissier, il faut récursive la plus grande pièce inférieure ou égale au montant encore pour compenser, [v for v in c if v<=x][0]loin, et compte le nombre de pièces utilisées, n.

La fonction non nommée retourne 1 si len(c)est inférieur à 3, et teste sinon que ce n'est pas le cas, 1-...que toute valeur dans la plage de possibilités range(c[0]*2)))est possible avec moins de pièces i in range(g(x,c)), en créant une collection de toutes les pièces, c*i, et en examinant toutes les combinaisons de ipièces de monnaie, combinations(c*i,i)pour voir si des sommes ont la même valeur.

Gelée ( fourchette ), 15 à 14 octets

SRæFµS€Ṃ=$Ṫµ€Ȧ

Cette solution utilise les bornes pour les contre-exemples de ce document . Là, l'auteur utilise une limite étroite pour le contre-exemple, mais dans l'intérêt du golf, la plage de la somme des dénominations de pièces est utilisée, ce qui est plus grand et contient cette limite.

Ce programme calcule tous les cas de test en moins d’une seconde sur ma machine.

Malheureusement, cela repose sur une branche de Jelly où je travaillais à la mise en œuvre d'un atome de résolution Frobenius, de sorte que vous ne pouvez pas l'essayer en ligne.

Usage

$ ./jelly eun 'SRæFµS€Ṃ=$Ṫµ€Ȧ' '1,2,4,6,8'
1

Les performances sont bonnes et peuvent résoudre tous les cas de test à la fois en moins d’une seconde.

$ time ./jelly eun 'SRæFµS€Ṃ=$Ṫµ€Ȧ¶Ç€' '[[1,3,4],[1,5,10,25],[1,6,10,25],[1,2,3],[1,8,17,30],[1,3,8,12],[1,2,8,13],[1,2,4,6,8]]'
[0, 1, 0, 1, 0, 0, 0, 1]

real    0m0.793s
user    0m0.748s
sys     0m0.045s

Explication

SRæFµS€Ṃ=$Ṫµ€Ȧ  Input: list of integers C
    µ           Start a new monadic chain
S                 Sum
 R                Range, [1, 2, ..., sum(C)]
  æF              Frobenius solve for each X in the range using coefficients from C
                  This generates all vectors where the dot product of a
                  vector with C equals X, ordered by using values from the
                  start to end of C
           µ€   Start a new monadic chain that operates on each list of vectors
     S€           Sum each vector
         $        Monadic hook on the sums
       Ṃ            Minimum (This is the optimal solution)
        =           Vectorized equals, 1 if true else 0
          Ṫ       Tail (This is at the index of the greedy solution)
             Ȧ  All, returns 0 if it contains a falsey value, else 1

JavaScript (ES6), 144 132 124 122 110 octets

a=>![...Array(a[0]*2)].some((_,i)=>(g=(a,l=0,n=i)=>[a.filter(c=>c>n||(l+=n/c|0,n%=c,0)),-l*!n])(...g(a))[1]>0)

Requiert que le tableau soit trié par ordre décroissant. Utilise l'observation dans le papier lié que si le système n'est pas canonique, il existe au moins une valeur inférieure à 2a [0] qui prend moins de pièces lorsqu'elle est décomposée à l'aide des pièces inutilisées de l'algorithme glouton initial.

Edit: Sauvegardé 12 octets en réalisant que je pouvais vérifier toutes les pièces même si j'avais déjà atteint la valeur cible. J'ai enregistré 8 octets en commutant ma sortie intermédiaire de [l,b]vers [b,-l]; cela m'a permis de passer directement le premier résultat en tant que paramètre du deuxième appel, ainsi qu'une petite sauvegarde détectant si le deuxième appel a réussi. J'ai enregistré 2 octets en déplaçant la définition de gdans le somerappel, me permettant d'éviter de passer inutilement deux fois dans la variable de boucle. J'ai enregistré 12 octets en passant de ma fonction d'assistance récursive à un appel à filter(rendu possible par mon commutateur de sortie intermédiaire).

Perl, 69 octets

Comprend +2 pour -pa

Donnez des pièces en ordre décroissant sur STDIN. Vous pouvez éventuellement laisser de côté la 1pièce.

coins.pl <<< "4 3 1"

coins.pl:

#!/usr/bin/perl -pa
$_=!map{grep$`>=$_&&($n=$G[$`-$_]+1)<($G[$`]||=$n),@F,/$/}1..2*"@F"

Construit le nombre de pièces utilisées par l’algorithme de la caisse @Gpour des montants allant de 1 à deux fois la plus grosse pièce. Pour chaque montant, vérifie que si ce montant est réduit d'une valeur d'une pièce, l'algorithme du caissier a besoin d'au plus une pièce de moins. Sinon, il s'agit d'un contre-exemple (ou il y avait un contre-exemple précédent). Je pourrais m'arrêter au premier contre-exemple, mais cela prend plus d'octets. Donc, la complexité temporelle est O(max_coin * coins)et la complexité spatiale estO(max_coin)