O algoritmo do caixa é um algoritmo para fazer alterações no número mínimo de moedas que funciona muito bem para a maioria dos sistemas monetários. No entanto, como a maioria dos algoritmos gananciosos, não deixa de ter suas falhas. Se um sistema de moeda estiver configurado da maneira certa (ou errada), existem certos valores nos quais o algoritmo do caixa não conseguirá encontrar a mudança ideal.

Veja o seguinte exemplo:

Temos moedas de 4 ¢, 3 ¢ e 1 ¢. Queremos fazer 6 ¢.

O algoritmo do caixa selecionará primeiro a maior moeda (uma 4 ¢ para iniciar) e subtrairá e repetirá. Isso resultará em uma moeda de 4 ¢ e duas moedas de 1 ¢, num total de 3 moedas.

Infelizmente para o algoritmo, há uma maneira de ganhar 6 ¢ com apenas duas moedas (duas de 3 ¢).

Um sistema de mudança será considerado canônico se, para todos os valores inteiros, o Algoritmo do Caixa encontrar o número ideal de moedas.

Tarefa

Sua tarefa será usar um sistema como um contêiner não ordenado ou contêiner ordenado ordenado de números inteiros representando valores de moedas e gerar um valor verdadeiro se a entrada do sistema for canônica e, caso contrário, será falsificada.

Seu programa deve funcionar para todos os sistemas que podem criar qualquer valor. (ou seja, todos os sistemas terão uma moeda de 1 ¢)

Este é o código de golfe que menos bytes ganha.

Casos de teste

Esta lista não é exaustiva, seu programa deve funcionar para todas as 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]

Essa solução funciona definindo uma função jque executa o algoritmo do caixa e informa quantas moedas o caixa usou. em seguida, verificamos o dobro do maior número da lista, supondo que o sistema tenha sido canônico para todos os números anteriores, que pegar a maior moeda possível é a escolha certa.

Esta solução assume que a entrada está classificada.

basta verificar o comprovante até o dobro do maior número: suponha que o sistema não seja canônico para algum número ie deixe ko número maior da lista não maior que i. assuma isso i >= 2ke o sistema é canônico para todos os números menores que i.

use uma maneira ideal de criar imoedas e assuma que ela não contém a moeda k. se jogarmos fora uma das moedas, a nova soma de moedas deve ser maior ke menor que i- mas o algoritmo do caixa nesse número usaria a kmoeda - e, portanto, esse conjunto de moedas pode ser substituído por um conjunto igual de moedas contendo a moeda ke, portanto, há um conjunto de moedas contendo a moeda kpara o número ie, por indução, o algoritmo do caixa retorna a melhor opção.

esse argumento realmente mostra que precisamos verificar apenas a soma dos dois maiores elementos - mas é mais demorado.

Edit: cinco bytes fora graças a Ørjan Johansen!

Pitão, 18 15 bytes

!x#eST.gsky_S*e

Suíte de teste

Um tipo diferente de força bruta. Isso começa formando todas as coleções de moedas com até k de cada uma, onde k é a maior moeda, que se supõe ser a última moeda. Eu acredito que isso sempre é suficiente para formar dois conjuntos de moedas com a mesma soma, uma gananciosa e outra mais curta, sempre que esse par existir.

Em seguida, localizo esse par da seguinte maneira:

Os subconjuntos são gerados em ordem crescente de tamanho e lexicograficamente por posição na entrada secundariamente. Agrupe as coleções de moedas por suas somas, de forma estável. Cada coleção de moedas é gerada em ordem decrescente, de modo que a solução gananciosa será o primeiro elemento do grupo, se e somente se a solução gananciosa for ótima, e será o último elemento do grupo lexicograficamente. Assim, encontramos a solução gananciosa e filtramos um índice diferente de zero no grupo. Se o conjunto de moedas for canônico, isso filtrará tudo, então simplesmente negamos logicamente o resultado e a saída.

Explicação:

!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

Da mesma forma que outras, conte as moedas até a soma dos dois últimos elementos da 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;

Minha melhor e mais longa resposta, acredito> 370 bytes

Dou apenas uma versão expandida porque é mais longa do que minha resposta 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;

Explicação para esta resposta

Versão Online

1. Defina tudo na matriz como false == X

2. Defina todos os números na matriz que você controla como S

3. Foram encontradas diferenças entre o último S e o outro S ou 0

4. Comece por último S na matriz

5. Defina todo o número como D Where Last S + uma de todas as diferenças

6. Comece em todos os D

7. DEFINIR "T" para D valores na matriz

8. GOTO 5 Repita-o com todos os DI encontrados, não realmente no código

9. Se o próximo item na matriz tiver X, é um caso falso, caso contrário, True

Etapas adicionais A diferença está no caso no trecho 3 Entre 1 e 4 são 2 X Isso significa que você precisa do segundo D da Etapa 5. Após esse valor nesse caso 10 são todos os casos verdadeiros, eu pude ver até o momento que existe um relacionamento entre a diferença e a contagem na matriz que você controla para calcular quanto D (Etapa 5) você precisa obter o ponto antes de encontrar o último caso falso.

Você define vários valores do último item diretamente para true. Esses pontos podem fazer a diferença para decidir se a contagem gananciosa de moedas com o próximo valor é igual à do múltiplo do último na matriz. Por outro lado, você pode definir inimigos

1. Defina o primeiro inimigo como 1 + Último S

2. A partir deste ponto, adicione cada valor na matriz para definir os próximos inimigos.

3. Comece com o último inimigo Goto 2

Se agora você tem inimigos e casos verdadeiros, aumenta a probabilidade de que as contagens possam ser as mesmas. Com mais D, a probabilidade diminui.

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>

mais? Bytes Obrigado @ JonathanAllan por me fornecer casos de teste errados
262 Bytes Quase, mas não o suficiente, 4 casos de teste incorretos no momento

casos de teste [1,16,256] antes devem ser verdadeiros após 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;

Ordem crescente da matriz

Explicação

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 o que vi na tabela contém valores de [1,2,3,4,5,6] e altero apenas o último item até 9. para 2to3 e 4to5, criamos o valor do valor mais baixo no cálculo do 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")

Isso precisa da matriz de entrada classificada em ordem decrescente. Para cada valor de 2N até 2 (N é o valor máximo da moeda), ele encontra o número de moedas do algoritmo ganancioso e tenta encontrar um conjunto menor de moedas.

Menos golfe

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
}

Teste

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, 21821115 bytes

-1 byte graças a @TuukkaX (um espaço pode ser excluído entre <3e 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 em ordem decrescente.

Força horrivelmente bruta. Qualquer conjunto de uma moeda unitária e outra moeda é canônico. Para conjuntos maiores, o menor caso de falha, se existir, será maior ou igual à 3ª menor moeda (não tenho certeza de como poderia ser igual!) E menor que a soma das duas maiores moedas - veja este documento (que na verdade referencia outro, mas também fornece um método O (n ^ 3)).

g conta as moedas usadas pelo método ganancioso, e a função sem nome percorre os possíveis candidatos (na verdade, de 0 a um a menos que o dobro da maior moeda para salvar bytes) e procura por qualquer coleção de menos moedas que também somam esse valor.

gtrabalha executando o que um caixa faria, recursivamente pega a maior moeda menor ou igual ao valor ainda a ser recuperado [v for v in c if v<=x][0]e conta e conta o número de moedas usadas n,.

A função sem nome retorna 1 se len(c)for menor que 3 e, caso contrário, testa que não é o caso, 1-...que quaisquer valores no intervalo de possibilidades range(c[0]*2)))são possíveis com menos moedas, i in range(g(x,c))criando uma coleção dessas muitas moedas, c*ie examinando todas as combinações de imoedas,, combinations(c*i,i)para ver se alguma soma tem o mesmo valor.

Gelatina ( garfo ), 15 14 bytes

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

Esta solução usa os limites para contra-exemplos deste documento . Lá, o autor usa um limite restrito para o contra-exemplo, mas, no interesse do golfe, é usado o intervalo da soma das denominações de moedas que é maior e contém esse limite.

Este programa calcula todos os casos de teste em menos de um segundo na minha máquina.

Infelizmente, isso depende de um ramo do Jelly, onde eu estava trabalhando na implementação de um átomo de solução Frobenius, para que você não possa experimentá-lo online.

Uso

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

O desempenho é bom e pode resolver todos os casos de teste de uma só vez em menos de um 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

Explicação

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

Requer que a matriz seja classificada em ordem decrescente. Usa a observação no artigo vinculado de que, se o sistema não for canônico, haverá pelo menos um valor menor que 2a [0], que exige menos moedas quando decomposto usando as moedas não utilizadas do algoritmo ganancioso inicial.

Edit: Salvo 12 bytes, percebendo que eu poderia verificar todas as moedas, mesmo que eu já tivesse atingido o valor alvo. Economizei 8 bytes alternando minha saída intermediária de [l,b]para [b,-l]; isso me permitiu passar o primeiro resultado diretamente como o parâmetro da segunda chamada, além de uma pequena economia detectando se a segunda chamada foi bem-sucedida. Economizei 2 bytes movendo a definição de gpara o someretorno de chamada, permitindo evitar passar desnecessariamente na variável de loop duas vezes. Economizei 12 bytes, alternando da minha função auxiliar recursiva para uma chamada para filter(possibilitada pela minha chave de saída intermediária).

Perl, 69 bytes

Inclui +2 para -pa

Dê moedas em ordem decrescente no STDIN. Opcionalmente, você pode deixar de fora a 1moeda.

coins.pl <<< "4 3 1"

coins.pl:

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

Constrói o número de moedas usadas pelo algoritmo dos caixas @Gpara montantes de 1 a duas vezes a maior moeda. Para cada quantia, verifique se, se essa quantia for reduzida em 1 valor de moeda, o algoritmo dos caixas precisará no máximo de 1 moeda a menos. Caso contrário, este é um contra-exemplo (ou houve um contra-exemplo anterior). Eu poderia parar no primeiro contra-exemplo, mas isso leva mais bytes. Portanto, a complexidade do tempo é O(max_coin * coins)e a complexidade do espaço éO(max_coin)