El Algoritmo del Cajero es un algoritmo para realizar cambios en la cantidad mínima de monedas que funciona bastante bien para la mayoría de los sistemas monetarios. Sin embargo, como la mayoría de los algoritmos codiciosos, no está exento de defectos. Si un sistema monetario está configurado correctamente (o simplemente incorrecto), hay ciertos valores en los cuales el Algoritmo del Cajero no podrá encontrar el cambio óptimo.

Tome el siguiente ejemplo:

Tenemos monedas de 4 ¢, 3 ¢ y 1 ¢. Queremos hacer 6 ¢.

El algoritmo del cajero seleccionará primero la mayor cantidad de monedas (una de 4 ¢ para comenzar) y restará y repetirá. Esto dará como resultado una moneda de 4 ¢ y dos monedas de 1 ¢, para un total de 3 monedas.

Desafortunadamente para el Algoritmo hay una manera de hacer 6 ¢ con solo dos monedas (dos monedas de 3 ¢).

Un sistema de cambio se considerará canónico si para todos los valores enteros el Algoritmo del Cajero encontrará la cantidad óptima de monedas.

Tarea

Su tarea será tomar un sistema como un contenedor no ordenado o un contenedor ordenado ordenado de enteros que representan valores de monedas y generar un valor verdadero si la entrada del sistema es canónica y falsa de lo contrario.

Su programa debería funcionar para todos los sistemas que puedan crear cualquier valor. (es decir, todos los sistemas tendrán una moneda de 1 ¢)

Este es el código de golf menos bytes gana.

Casos de prueba

Esta lista no es exhaustiva, su programa debería funcionar para todas las entradas válidas

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 bytes

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]

esta solución funciona definiendo una función jque realiza el algoritmo del cajero y nos dice cuántas monedas usó el cajero. luego verificamos hasta el doble del número más grande en la lista, suponiendo que el sistema ha sido canónico para todos los números anteriores, que tomar la moneda más grande posible es la opción correcta.

Esta solución supone que la entrada está ordenada.

la comprobación de pruebas hasta el doble del número más grande es suficiente: suponga que el sistema no es canónico para algún número i, y deje kque el número más grande en la lista no sea mayor i. suponga eso i >= 2ky el sistema es canónico para todos los números menores que i.

tome una forma óptima de hacer imonedas y suponga que no contiene la moneda k. si tiramos una de las monedas, la nueva suma de monedas debe ser mayor ky menor que i, pero el algoritmo del cajero en este número usaría la kmoneda, y por lo tanto, este conjunto de monedas se puede reemplazar con un conjunto igual de monedas que contiene la moneda ky, por lo tanto, hay un conjunto de monedas que contiene la moneda kpara el número iy, por inducción, el algoritmo del cajero devuelve la opción óptima.

Este argumento realmente muestra que solo necesitamos verificar hasta la suma de los dos elementos más grandes, pero es más largo hacerlo.

Editar: cinco bytes de descuento gracias a Ørjan Johansen!

Pyth, 18 15 bytes

!x#eST.gsky_S*e

Banco de pruebas

Un tipo diferente de fuerza bruta. Esto comienza formando todas las colecciones de monedas con hasta k de cada una, donde k es la moneda más grande, que se supone que es la última moneda. Creo que esto siempre es suficiente para formar dos juegos de monedas con la misma suma, una codiciosa y otra más corta, siempre que exista tal par.

Luego ubico un par de este modo:

Los subconjuntos se generan en orden de tamaño creciente, y lexicográficamente por posición en la entrada secundaria. Agrupe las colecciones de monedas por sumas, de manera estable. Cada colección de monedas se genera en orden descendente, por lo que la solución codiciosa será el primer elemento del grupo si y solo si la solución codiciosa es óptima, y ​​será el último elemento del grupo lexicográficamente. Por lo tanto, encontramos la solución codiciosa y filtramos en un índice distinto de cero en el grupo. Si el conjunto de monedas es canónico, esto filtrará todo, por lo que simplemente negamos lógicamente el resultado y la salida.

Explicación:

!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 bytes

Del mismo modo que otros, cuente las monedas hasta la suma de los dos últimos elementos de la matriz

<?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;

Mi mejor y más larga respuesta creo> 370 Bytes

Solo doy una versión ampliada porque es más larga que mi respuesta antes

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;

Explicación de esta respuesta.

Versión en línea

1. Establezca todo en la matriz en falso == X

2. Establezca todos los números en la matriz que controla en S

3. Se encontraron diferencias entre la última S y la otra S o 0

4. Comience en la última S en la matriz

5. Establezca todos los números en D donde última S + una de todas las diferencias

6. Comience en todo D

7. SET "T" a los valores D en la matriz

8. GOTO 5 Repítalo con todos los DI encontrados, realmente no lo hizo en el código

9. Si el siguiente elemento de la matriz tiene X, es un caso falso, de lo contrario es verdadero

Pasos adicionales La diferencia está en el caso en el fragmento 3 Entre 1 y 4 son 2 X Esto significa que necesita la segunda D en el Paso 5. Después de este valor en este caso 10 son todos los casos verdaderos que pude ver hasta ahora que hay una relación entre la diferencia y la cuenta en la matriz que controlas para calcular cuánto D (Paso 5) necesitas para obtener el punto antes de encontrar el último caso falso.

Establece varios valores desde el último elemento directamente a verdadero. Estos puntos pueden marcar la diferencia para decidir si podría ser que el codicioso conteo de monedas con el siguiente valor sea el mismo que el múltiplo de los últimos en la matriz. Por otro lado puedes establecer enemigo

1. Establecer primer enemigo en 1 + Última S

2. Desde este punto, agregue cada valor en la matriz para establecer los siguientes enemigos

3. Comience con el último enemigo Goto 2

Si ahora tiene enemigos y casos verdaderos, aumenta la probabilidad de que los recuentos puedan ser los mismos. Con más D, la probabilidad disminuye.

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>

más? Bytes Gracias @ JonathanAllan por darme casos de prueba incorrectos
262 Bytes Casi pero no lo suficientemente bueno 4 casos de prueba incorrectos en el momento

casos de prueba [1,16,256] antes debe ser verdadero después de falso

<?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;

Orden ascendente de la matriz

Explicación

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

Parece que lo que he visto en la tabla contiene valores de [1,2,3,4,5,6] y solo cambio el último elemento hasta 9. Para 2to3 y 4to5 creamos el valor del valor más bajo en cálculo de módulo

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")

Esto necesita la matriz de entrada ordenada en orden descendente. Para cada valor de 2N downto 2 (N es el valor máximo de la moneda), encuentra el número de monedas del algoritmo codicioso e intenta encontrar un conjunto más pequeño de monedas.

Menos 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
}

Prueba

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 bytes

-1 byte gracias a @TuukkaX (se puede eliminar un espacio entre <3y 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

Entrada en orden descendente.

Horriblemente fuerza bruta. Cualquier conjunto de monedas de una sola unidad y alguna otra moneda es canónico. Para conjuntos más grandes, el caso de falla más pequeño, si existe, será mayor o igual que la tercera moneda más pequeña (¡no estoy seguro de cómo podría ser igual!) Y menor que la suma de las dos monedas más grandes; vea este documento (que en realidad hace referencia a otro pero también da un método O (n ^ 3)).

g cuenta las monedas utilizadas por el método codicioso, y la función sin nombre atraviesa los posibles candidatos (en realidad, de 0 a una menos del doble de la moneda más grande para ahorrar bytes) y busca cualquier colección de menos monedas que también sumen esa cantidad.

gfunciona mediante la realización de un cajero lo haría, de forma recursiva toma la moneda más grande menor o igual al importe que aún conforman, [v for v in c if v<=x][0]de distancia, y llega hasta el número de monedas utilizadas, n.

La función sin nombre devuelve 1 si len(c)es menor que 3, y de lo contrario prueba que no es el caso, 1-...que cualquier valor en el rango de posibilidades range(c[0]*2))), es posible con menos monedas i in range(g(x,c)), al hacer una colección de esa cantidad de cada moneda, c*iy examinando todas las combinaciones de imonedas, combinations(c*i,i)para ver si alguna suma al mismo valor.

Gelatina ( tenedor ), 15 14 bytes

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

Esta solución utiliza los límites para contraejemplos de este documento . Allí, el autor utiliza un límite estricto para el contraejemplo, pero en interés del golf, se utiliza el rango de la suma de las denominaciones de monedas que es más grande y contiene ese límite.

Este programa calcula todos los casos de prueba en menos de un segundo en mi máquina.

Desafortunadamente, esto se basa en una rama de Jelly donde estaba trabajando en la implementación de un átomo de solución de Frobenius para que no pueda probarlo en línea.

Uso

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

El rendimiento es bueno y puede resolver todos los casos de prueba a la vez en menos de un segundo.

$ 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

Explicación

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 bytes

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)

Requiere que la matriz se ordene en orden descendente. Utiliza la observación en el documento vinculado de que si el sistema no es canónico, entonces hay al menos un valor menor que 2a [0] que toma menos monedas cuando se descompone usando las monedas no utilizadas del algoritmo codicioso inicial.

Editar: ahorré 12 bytes al darme cuenta de que podía verificar todas las monedas a pesar de que ya había alcanzado el valor objetivo. Ahorré 8 bytes cambiando mi salida intermedia de [l,b]a [b,-l]; Esto me permitió pasar el primer resultado directamente como el parámetro de la segunda llamada, además de un pequeño ahorro para detectar si la segunda llamada fue exitosa. Ahorré 2 bytes moviendo la definición de gen la somedevolución de llamada, lo que me permite evitar pasar innecesariamente la variable de bucle dos veces. Ahorré 12 bytes al cambiar de mi función auxiliar recursiva a una llamada a filter(hecho posible por mi interruptor de salida intermedio).

Perl, 69 bytes

Incluye +2 para -pa

Dar monedas en orden descendente en STDIN. Opcionalmente, puede dejar de lado la 1moneda.

coins.pl <<< "4 3 1"

coins.pl:

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

Acumula el número de monedas utilizadas por el algoritmo de cajero en @Gcantidades de 1 a dos veces la moneda más grande. Para cada cantidad, comprueba que si esa cantidad se reduce en 1 valor de moneda, el algoritmo de cajero necesita como máximo 1 moneda menos. Si no, este es un contraejemplo (o hubo un contraejemplo anterior). Podría detenerme en el primer contraejemplo, pero eso requiere más bytes. Entonces, la complejidad del tiempo es O(max_coin * coins)y la complejidad del espacio esO(max_coin)