В алгоритме кассира представляет собой алгоритм для внесения изменения в минимальном количестве монет , который работает достаточно хорошо для большинства валютных систем. Однако, как и большинство жадных алгоритмов, он не лишен недостатков. Если валютная система настроена правильно (или просто неправильно), существуют определенные значения, в которых алгоритм Кассира не сможет найти оптимальное изменение.

Возьмите следующий пример:

У нас есть 4, 3 и 1 монеты. Мы хотим сделать 6 ¢.

Алгоритм кассира сначала выберет как можно больше наибольшей монеты (одна 4 ¢ для начала), вычтет и повторит. Это приведет к одной 4 ¢ монете и двум 1 ¢ монетам, всего 3 монеты.

К сожалению, для алгоритма есть способ сделать 6 ¢ только с двумя монетами (две 3 ¢ монеты).

Система изменений будет считаться канонической, если для всех целочисленных значений алгоритм Кассира найдет оптимальное количество монет.

задача

Ваша задача состоит в том, чтобы взять систему в качестве неупорядоченного контейнера или отсортированного упорядоченного контейнера целых чисел, представляющих значения монет, и вывести истинное значение, если системный ввод является каноническим, а в противном случае - ошибочным.

Ваша программа должна работать для всех систем, которые могут создавать любую ценность. (т.е. все системы будут иметь монету в 1 цент)

Это код гольф наименьшего количества байтов.

Контрольные примеры

Этот список ни в коем случае не является исчерпывающим, ваша программа должна работать со всеми допустимыми данными

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 байта

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]

Это решение работает путем определения функции, jкоторая выполняет алгоритм кассира и сообщает нам, сколько монет использовала кассир. Затем мы проверяем вдвое больше самого большого числа в списке, предполагая, что система была канонической для всех предыдущих чисел, что выбор самой большой возможной монеты - правильный выбор.

это решение предполагает, что вход отсортирован.

Для проверки достаточно удвоить наибольшее число: предположим, что система не является канонической для некоторого числа i, и пусть это kбудет самое большое число в списке, не превышающее i. Предположим, что i >= 2kи система является канонической для всех чисел меньше, чем i.

Возьмите какой-нибудь оптимальный способ сделать iиз монет, и предположите, что это не содержит монету k. если мы выбрасываем одну из монет, новая сумма монет должна быть больше kили меньше чем i- но алгоритм кассира на этом числе будет использовать kмонету - и, следовательно, этот набор монет можно заменить равным набором монет содержит монету k, и, следовательно, есть набор монет, содержащий монету kдля числа i, и по индукции алгоритм кассира возвращает оптимальный выбор.

этот аргумент действительно показывает, что нам нужно проверять только сумму двух самых больших элементов - но это занимает больше времени.

Редактировать: пять байтов от благодаря Эрджану Йохансену!

Pyth, 18 15 байт

!x#eST.gsky_S*e

Тестирование

Другой вид грубой силы. Это начинается с формирования всех коллекций монет с максимум k каждой, где k - самая большая монета, которая считается последней монетой. Я считаю, что этого всегда достаточно, чтобы сформировать два набора монет с одинаковой суммой, один жадный и один короче, когда такая пара существует.

Затем я нахожу такую ​​пару следующим образом:

Подмножества генерируются в порядке возрастания размера и лексикографически по положению на входе вторично. Сгруппируйте коллекции монет по суммам, стабильно. Каждая коллекция монет генерируется в порядке убывания, поэтому жадное решение будет первым элементом группы тогда и только тогда, когда жадное решение является оптимальным, и оно будет последним элементом лексикографически группы. Таким образом, мы находим жадное решение и фильтруем по ненулевому индексу в группе. Если набор монет канонический, это отфильтрует все, поэтому мы просто логически отрицаем результат и вывод.

Объяснение:

!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 байта

Так же, как и другие, считать монеты до суммы двух последних элементов в массиве

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

Мой лучший и самый длинный ответ, я верю> 370 байт

Я даю только расширенную версию, потому что она длиннее моего ответа

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;

Пояснение к этому ответу

Онлайн версия

1. Установить все в массиве на false == X

2. Установите все числа в массиве под вашим контролем на S

3. Найдены различия между последним S и другим S или 0

4. Начать, наконец, S в массиве

5. Установите все числа на D, где Last S + одно из всех различий

6. Начни вообще D

7. УСТАНОВИТЕ «T» в D значения в массиве

8. GOTO 5 Повторите это со всеми найденными D Я сделал это не совсем в коде

9. Если следующий элемент в массиве имеет X, это ложный случай, иначе True

Дополнительные шаги Разница в случае во фрагменте 3 От 1 до 4 равны 2 X Это означает, что вам нужен второй D к шагу 5. После того, как это значение в этом случае 10 все случаи истинны, я мог видеть, что существует связь между разницей и количеством в массиве, которым вы управляете, чтобы вычислить, сколько D (шаг 5) вам нужно, чтобы получить точку, прежде чем вы найдете последний ложный случай.

Вы устанавливаете несколько значений из последнего элемента непосредственно в true. Эти Точки могут иметь значение, чтобы решить, могло ли быть, что жадное число монет со следующим значением такое же, как и кратное последнему в массиве. На другой путь вы можете установить противника

1. Установите первого врага на 1 + Last S

2. С этой точки добавьте каждое значение в массив, чтобы установить следующих врагов

3. Начните с последнего врага Goto 2

Если у вас теперь есть враги и истинные случаи, вероятность возрастает, что количество может быть одинаковым. Чем больше D, тем меньше вероятность.

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>

плюс? Bytes Спасибо @JonathanAllan за неправильные контрольные примеры
262 байта Почти, но не достаточно 4 неправильных контрольных примера в данный момент

контрольные примеры [1,16,256] перед должны истина после ложного

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

Восходящий порядок массива

объяснение

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

Похоже, что то, что я видел, таблица содержит значения из [1,2,3,4,5,6], и я меняю только последний элемент до 9. Для 2to3 и 4to5 мы создаем значение более низкого значения в расчет по модулю

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

Для этого необходимо, чтобы входной массив был отсортирован в порядке убывания. Для каждого значения от 2N до 2 (N является максимальным значением монеты), он находит количество монет из жадного алгоритма и пытается найти меньший набор монет.

Меньше гольфа

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
}

Контрольная работа

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 байт

-1 байт благодаря @TuukkaX (пробел может быть удален между <3и 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

Ввод в порядке убывания.

Ужасная грубая сила. Любой набор монеты из одной единицы и другой монеты является каноническим. Для больших наборов наименьший случай неудачи, если он существует, будет больше или равен 3-й самой маленькой монете (не уверен сам, как она может быть равной!) И меньше суммы двух самых больших монет - см. Эту статью (которая на самом деле ссылается на другой, но также дает метод O (n ^ 3).

g подсчитывает монеты, используемые жадным методом, а безымянная функция обходит возможные кандидаты (фактически от 0 до одной, в два раза меньшей, чем самая большая монета для сохранения байтов) и ищет любую коллекцию из меньшего числа монет, которая также суммируется с этой суммой.

gработает, выполняя то , что кассир будет, она рекурсивно занимает самую большую монету меньше или равна сумме , по- прежнему , чтобы компенсировать , [v for v in c if v<=x][0]прочь, и подсчитывает количество монет , используемых n.

Безымянная функция возвращает 1, если len(c)меньше 3, и в противном случае проверяет, что это не так, 1-...что любые значения в диапазоне возможностей range(c[0]*2)))возможны при меньшем количестве монет i in range(g(x,c))путем создания коллекции такого количества каждой монеты, c*iи исследуя все комбинации iмонет, combinations(c*i,i)чтобы узнать, есть ли какая-либо сумма к одному и тому же значению.

Желе ( вилка ), 15 14 байт

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

Это решение использует границы контрпримеров из этой статьи . Там автор использует жесткую границу для контрпримера, но в интересах игры в гольф используется диапазон суммы номиналов монет, который больше и содержит эту границу.

Эта программа вычисляет все тестовые случаи менее чем за секунду на моей машине.

К сожалению, это зависит от ветки Jelly, где я работал над реализацией атома решения Frobenius, поэтому вы не можете попробовать это онлайн.

использование

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

Производительность хорошая и может решить все тестовые случаи одновременно менее чем за секунду.

$ 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

объяснение

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 байтов

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)

Требует сортировки массива в порядке убывания. Использует наблюдение в связанной статье, что если система не является канонической, то существует хотя бы одно значение меньше 2a [0], которое требует меньше монет при разложении с использованием неиспользованных монет из исходного алгоритма жадности.

Изменить: 12 байт, поняв, что я могу проверить все монеты, даже если я уже достиг целевого значения. Сэкономил 8 байтов, переключив мой промежуточный выход с [l,b]на [b,-l]; это позволило мне передать первый результат непосредственно в качестве параметра второго вызова, а также небольшое сохранение, определяющее, был ли второй вызов успешным. Сэкономили 2 байта, переместив определение gв someобратный вызов, что позволило мне избежать ненужной передачи переменной цикла дважды. Сэкономили 12 байт, переключившись с моей рекурсивной вспомогательной функции на вызов filter(стало возможным благодаря моему промежуточному выходному переключателю).

Perl, 69 байт

Включает +2 для -pa

Дайте монеты в порядке убывания на STDIN. При желании вы можете оставить 1монету.

coins.pl <<< "4 3 1"

coins.pl:

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

Наращивает количество монет, используемых алгоритмом кассира, @Gна суммы от 1 до двойной самой большой монеты. Для каждой суммы проверяется, что, если эта сумма уменьшается на 1 монету, алгоритму кассира требуется не более 1 монеты меньше. Если нет, то это контрпример (или ранее был контрпример). Я мог бы остановиться на первом контрпримере, но это занимает больше байтов. Таким образом, сложность времени есть, O(max_coin * coins)а сложность пространстваO(max_coin)