The Algoritma Tunai ini adalah algoritma untuk membuat perubahan dalam jumlah minimal koin yang bekerja cukup baik untuk sebagian besar sistem mata uang. Namun seperti kebanyakan algoritma serakah itu bukan tanpa kekurangannya. Jika sistem mata uang diatur tepat (atau salah) ada nilai-nilai tertentu di mana Algoritma Kasir akan gagal menemukan perubahan optimal.

Ambil contoh berikut:

Kami memiliki 4 ¢, 3 ¢, dan 1 ¢ koin. Kami ingin membuat 6 ¢.

Algoritma Kasir pertama-tama akan memilih sebanyak mungkin koin terbesar (satu 4 ¢ untuk memulai) dan kurangi dan ulangi. Ini akan menghasilkan satu koin 4 ¢ dan dua koin 1 ¢, dengan total 3 koin.

Sayangnya untuk Algoritma ada cara untuk membuat 6 ¢ dengan hanya dua koin (dua koin 3 ¢).

Sistem perubahan akan dianggap iff kanonik untuk semua nilai integer Algoritma Kasir akan menemukan jumlah koin yang optimal.

Tugas

Tugas Anda adalah mengambil sistem sebagai wadah tidak berurutan atau wadah bilangan bulat berurutan yang diurutkan yang mewakili nilai koin dan menghasilkan nilai kebenaran jika input sistem kanonik dan palsu sebaliknya.

Program Anda harus bekerja untuk semua sistem yang dapat menciptakan nilai apa pun. (yaitu semua sistem akan memiliki koin 1 ¢)

Ini adalah kode golf paling tidak byte yang menang.

Uji kasus

Daftar ini sama sekali tidak lengkap, program Anda harus bekerja untuk semua input yang valid

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 byte

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]

solusi ini bekerja dengan mendefinisikan fungsi jyang menjalankan algoritma kasir dan memberi tahu kami berapa banyak koin yang digunakan kasir. kami kemudian memeriksa hingga dua kali angka terbesar dalam daftar, dengan asumsi bahwa sistem telah kanonik untuk semua angka sebelumnya, bahwa mengambil koin sebanyak mungkin adalah pilihan yang tepat.

solusi ini mengasumsikan input diurutkan.

bukti memeriksa hingga dua kali jumlah terbesar sudah cukup: anggap sistem tidak kanonik untuk beberapa nomor i, dan biarkan knomor terbesar dalam daftar tidak lebih besar dari i. menganggap itu i >= 2kdan sistem adalah kanonik untuk semua angka kurang dari i.

mengambil beberapa cara optimal untuk membuat ikoin, dan menganggap itu tidak mengandung koin k. jika kita membuang salah satu koin, jumlah koin yang baru harus lebih besar daripada kdan lebih kecil dari i- tetapi algoritma kasir pada nomor ini akan menggunakan kkoin - dan karenanya, set koin ini dapat diganti dengan set koin yang sama mengandung koin k, dan oleh karena itu ada satu set koin yang berisi koin kuntuk nomor tersebut i, dan dengan induksi algoritma kasir mengembalikan pilihan optimal.

argumen ini benar-benar menunjukkan bahwa kita hanya perlu memeriksa sampai jumlah dari dua elemen terbesar - tetapi lebih panjang untuk melakukannya.

Sunting: lepas lima byte berkat Ørjan Johansen!

Pyth, 18 15 byte

!x#eST.gsky_S*e

Suite uji

Semacam kekuatan brutal yang berbeda. Ini dimulai dengan membentuk semua koleksi koin hingga masing-masing k, di mana k adalah koin terbesar, yang dianggap sebagai koin terakhir. Saya percaya ini selalu cukup untuk membentuk dua set koin dengan jumlah yang sama, satu serakah dan satu lebih pendek, setiap kali pasangan semacam itu ada.

Saya kemudian menemukan pasangan seperti itu sebagai berikut:

Subhimpunan dihasilkan dalam urutan ukuran meningkat, dan secara leksikografis oleh posisi di input kedua. Kelompokkan koleksi koin dengan jumlah mereka, secara stabil. Setiap koleksi koin dihasilkan dalam urutan menurun, sehingga solusi serakah akan menjadi elemen pertama grup jika dan hanya jika solusi serakah optimal, dan itu akan menjadi elemen terakhir grup secara leksikografis. Jadi, kami menemukan solusi serakah, dan memfilter pada indeks bukan nol di grup. Jika set koin adalah kanonis, ini akan memfilter semuanya, jadi kami secara logis meniadakan hasil dan output.

Penjelasan:

!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

Cara yang sama seperti lainnya menghitung koin sampai jumlah dari dua elemen terakhir dalam array

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

Jawaban terbaik dan terpanjang saya, saya percaya> 370 Bytes

Saya hanya memberikan versi yang diperluas karena lebih lama dari jawaban saya sebelumnya

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;

Penjelasan untuk jawaban ini

Versi Online

1. Setel semua dalam array ke false == X

2. Setel semua angka dalam larik yang Anda kontrol ke S

3. Ditemukan perbedaan antara S terakhir dan S lainnya atau 0

4. Mulai S terakhir dalam array

5. Setel semua angka ke D Di mana S Terakhir adalah salah satu dari semua perbedaan

6. Mulai sama sekali D

7. SET "T" ke nilai D dalam array

8. GOTO 5 Ulangi dengan semua yang ditemukan DI tidak melakukannya dalam kode

9. Jika item berikutnya dalam Array memiliki X itu adalah kasus yang salah lagi Benar

Perbedaan Langkah Tambahan dalam kasus dalam cuplikan 3 Antara 1 dan 4 adalah 2 X Ini berarti Anda memerlukan D kedua pada Langkah 5. Setelah nilai ini dalam kasus ini 10 semuanya benar, saya bisa melihat sejauh ini bahwa ada hubungan antara perbedaan dan jumlah dalam array yang Anda kontrol untuk menghitung berapa banyak D (Langkah 5) yang Anda butuhkan untuk mendapatkan poin sebelum Anda menemukan kasus palsu terakhir.

Anda menetapkan beberapa nilai dari item terakhir langsung ke true. Poin-poin ini dapat membuat perbedaan untuk memutuskan apakah bisa saja jumlah serakah dari koin dengan nilai berikutnya sama maka kelipatan yang terakhir dalam array. Di sisi lain Anda dapat mengatur musuh

1. Tetapkan musuh pertama di 1 + S Terakhir

2. Dari titik ini, tambahkan setiap nilai dalam array untuk mengatur musuh berikutnya

3. Mulai dengan Goto 2 musuh terakhir

Jika sekarang Anda memiliki musuh dan kasus nyata di dalamnya probabilitas tumbuh bahwa jumlah bisa sama Dengan lebih banyak D probabilitas tenggelam.

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 Terima Kasih @JonathanAllan memberi saya test case yang salah
262 Bytes Hampir tidak cukup baik 4 testcase salah saat ini

kasus uji [1,16.256] sebelumnya harus benar setelah salah

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

Urutan Array yang Meningkat

Penjelasan

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

Sepertinya tabel yang saya lihat berisi nilai dari [1,2,3,4,5,6] dan saya hanya mengubah item terakhir sampai 9. untuk 2to3 dan 4to5 kita membuat nilai dari nilai yang lebih rendah di perhitungan 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")

Ini membutuhkan array input yang diurutkan dalam urutan menurun. Untuk setiap nilai dari 2N hingga 2 (N menjadi nilai maksimum koin), ia menemukan jumlah koin dari algoritme serakah dan mencoba menemukan kumpulan koin yang lebih kecil.

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

Uji

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 byte

-1 byte berkat @TuukkaX (spasi dapat dihapus antara <3dan 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

Masukan dalam urutan menurun.

Kekuatan brutal yang mengerikan. Setiap set koin satuan tunggal dan beberapa koin lainnya adalah kanonik. Untuk set yang lebih besar, case kegagalan terkecil, jika ada, akan lebih besar dari atau sama dengan koin terkecil ke-3 (tidak yakin sendiri bagaimana bisa setara!) Dan kurang dari jumlah dua koin terbesar - lihat tulisan ini (yang sebenarnya referensi yang lain tetapi juga memberikan metode O (n ^ 3)).

g menghitung koin yang digunakan dengan metode serakah, dan fungsi yang tidak disebutkan namanya melintasi kandidat yang mungkin (sebenarnya dari 0 menjadi satu kurang dari dua kali koin terbesar untuk menghemat byte) dan mencari koleksi koin yang lebih sedikit yang juga menjumlahkan jumlah itu.

gbekerja dengan melakukan apa yang akan dilakukan seorang kasir, secara rekursif mengambil koin terbesar kurang dari atau sama dengan jumlah yang masih dibuat, [v for v in c if v<=x][0]hilang, dan menghitung jumlah koin yang digunakan n,.

Fungsi yang tidak disebutkan namanya mengembalikan 1 jika len(c)kurang dari 3, dan sebaliknya menguji bahwa tidak demikian halnya,, 1-...bahwa nilai apa pun dalam kisaran kemungkinan, range(c[0]*2)))dimungkinkan dengan koin yang lebih sedikit i in range(g(x,c)),, dengan membuat koleksi yang banyak dari setiap koin, c*i, dan memeriksa semua kombinasi ikoin combinations(c*i,i),, untuk melihat apakah ada jumlah dengan nilai yang sama.

Jelly ( garpu ), 15 14 byte

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

Solusi ini menggunakan batas untuk contoh tandingan dari makalah ini . Di sana, penulis menggunakan ikatan ketat untuk contoh tandingan, tetapi untuk kepentingan bermain golf, kisaran jumlah denominasi koin digunakan yang lebih besar dan berisi ikatan itu.

Program ini menghitung semua test case dalam waktu kurang dari sedetik di mesin saya.

Sayangnya, ini bergantung pada cabang Jelly tempat saya bekerja mengimplementasikan atom pemecah Frobenius sehingga Anda tidak dapat mencobanya secara online.

Pemakaian

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

Performanya bagus dan dapat menyelesaikan semua kasus uji sekaligus dalam waktu kurang dari satu detik.

$ 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

Penjelasan

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 byte

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)

Membutuhkan array yang akan diurutkan dalam urutan menurun. Menggunakan pengamatan di kertas yang ditautkan bahwa jika sistem ini tidak kanonik maka ada setidaknya satu nilai kurang dari 2a [0] yang membutuhkan lebih sedikit koin ketika didekomposisi menggunakan koin yang tidak digunakan dari algoritma serakah awal.

Sunting: Disimpan 12 byte dengan menyadari bahwa saya dapat memeriksa semua koin meskipun saya telah mencapai nilai target. Disimpan 8 byte dengan mengalihkan output antara saya dari [l,b]ke [b,-l]; ini memungkinkan saya untuk melewatkan hasil pertama secara langsung sebagai parameter dari panggilan kedua, ditambah juga penghematan kecil yang mendeteksi apakah panggilan kedua berhasil. Disimpan 2 byte dengan memindahkan definisi gke dalam somecallback, memungkinkan saya untuk menghindari yang tidak perlu melewati variabel loop dua kali. Disimpan 12 byte dengan beralih dari fungsi pembantu rekursif saya ke panggilan ke filter(dimungkinkan oleh saklar keluaran antara saya).

Perl, 69 byte

Termasuk +2 untuk -pa

Berikan koin dalam urutan menurun pada STDIN. Anda dapat meninggalkan 1koin secara opsional .

coins.pl <<< "4 3 1"

coins.pl:

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

Membangun jumlah koin yang digunakan oleh algoritma kasir @Guntuk jumlah 1 hingga dua kali koin terbesar. Untuk setiap jumlah memeriksa bahwa jika jumlah itu dikurangi dengan 1 nilai koin, algoritma kasir membutuhkan paling banyak 1 koin kurang. Jika tidak, ini adalah sampel tandingan (atau ada sampel tandingan sebelumnya). Saya bisa berhenti pada counterexample pertama tetapi itu membutuhkan lebih banyak byte. Jadi kompleksitas waktu O(max_coin * coins)dan kompleksitas ruangO(max_coin)