Napisz program, który oblicza, czy wprowadzona wartość pieniężna, jako liczba całkowita, może być reprezentowana przez unikalną kombinację monet i / lub banknotów, co oznacza, że ​​tej samej monety / banknoty nie można użyć więcej niż jeden raz.

Twój program powinien przyjmować wartość jako dane wejściowe i może pobierać listę wartości monet / banknotów przez dane wejściowe lub przez odpowiednik tablicy w Twoim języku. Lista monet / banknotów powinna być w stanie się zmieniać, więc upewnij się, że jest jasne, gdzie to jest zdefiniowane, jeśli używasz stałej.

Twój program powinien wypisać odpowiednio dowolną wartość prawdy / fałszu.

Należy pamiętać, że generowanie listy monet / banknotów, które składają się na wartość, nie jest wymagane.

PRZYKŁAD

Przy użyciu funta brytyjskiego (1,00 GBP = 100 i 420,69 GBP = 42069)

coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000]

Następujące wartości wyjściowe będą prawdziwe:

6 (1, 5)
15 (10, 5)
88 (1, 2, 5, 10, 20, 50)
512 (500, 10, 2)
7003 (5000, 2000, 2, 1)

Poniższe wyświetli wartość false:

4
209
8889
4242424242
[ANYTHING ABOVE 8888]

ALTERNATYWNE DANE TESTOWE (dolar amerykański)

coins = [1, 5, 10, 25, 50, 100, 200, 500, 1000, 2000, 5000, 10000]

Powodzenia!

Brachylog 2 (TIO Nexus), 2 bajty

⊇+

Wypróbuj online!

Pobiera listę monet albo za pomocą standardowego wejścia, albo przygotowując ją na początek programu jako literał tablicowy (każda z nich będzie działać, więc to od ciebie zależy, co uważasz za „bardziej uzasadnione”; ta pierwsza jest domyślnie dozwolona Zasady PPCG, te ostatnie są wyraźnie dozwolone w pytaniu); i przyjmuje wartość do wygenerowania jako argument wiersza polecenia.

Wyjaśnienie

Ten program wykorzystuje szczegóły implementacji sposobu, w jaki opakowanie TIO Nexus dla funkcji Brachylog; w szczególności pozwala podać argument wiersza poleceń, aby podać dane wejściowe za pośrednictwem Output. (Nie było to przewidziane w oryginalnym projekcie Brachylog; jednak języki są definiowane przez ich implementację w PPCG, a jeśli pojawi się implementacja, która akurat robi to, czego potrzebuję, mogę z tego skorzystać.) program wygląda następująco:

⊇+
⊇   Some subset of {standard input}
 +  sums to {the first command-line argument}

Jako pełny program zwraca wartość logiczną; true.czy wszystkie twierdzenia w programie mogą być jednocześnie spełnione, lub false.jeśli nie mogą.

(Przypomnienie lub dla osób, które jeszcze nie wiedzą: Brachylog 2 używa własnego kodowania znaków, w którym ⊇jest to jeden bajt.)

05AB1E , 4 bajty

æOså

Wyjaśnienie:

æ      Calculate the powerset of the first input
 O     Sum each element
  s    Put the second input at the top of the stack
   å   Check whether the input is in the powerset sum.

Wypróbuj online!

Mathematica, 25 bajtów

!FreeQ[Tr/@Subsets@#,#2]&

Czysta funkcja przyjmująca tablicę wartości monet jako pierwszy argument i docelową liczbę całkowitą jako drugi argument i zwracająca Truelub False.

Galaretka, 6 bajtów

ŒPS€e@

Wypróbuj online!

-2 bajty dzięki Leaky Nun
-13 bajtów dzięki Leaky Nun (długa historia)

Siatkówka , 52 31 bajtów

\d+
$*
^((1+) |1+ )+(?<-2>\2)+$

Wypróbuj online! Pobiera dane wejściowe jako rozdzieloną spacjami listę monet i banknotów, po której następuje żądana wartość. Edycja: Zapisałem 18 bajtów dzięki @Kobi, który debugował mój kod. Objaśnienie: Pierwsze dwa wiersze po prostu konwertują z dziesiętnego na jednoargumentowy. Trzeci wiersz przechwytuje listę monet i banknotów. Ta zmiana umożliwia silnikowi cofnięcie się i wybranie opcji, aby nie przechwytywać określonych monet / banknotów. Grupa bilansująca dopasowuje następnie wartość do wszystkich przyrostków listy przechwytywania (niepotrzebne, ale bardziej golfowe).

Brachylog , 7 bajtów

tT&h⊇+T

Wypróbuj online!

Jak to działa

tT&h⊇+T
tT      the second input is T
  &     and
   h    the first input
    ⊇   is a superset of a set
     +  that sums up to
      T T

Łącznie z kombinacją, 9 bajtów

tT&h⊇.+T∧

Wypróbuj online!

Java (OpenJDK 8) , 125 bajtów

boolean f(int[]c,int n){int l=c.length;if(l<1)return n==0;int[]a=java.util.Arrays.copyOf(c,l-1);return f(a,n-c[l-1])|f(a,n);}

Wypróbuj online!

Prolog (SWI) , 46 bajtów

a([],0).
a([H|T],X):-Y is X-H,(a(T,Y);a(T,X)).

Wypróbuj online!

Widelec mojej odpowiedzi w języku Python .

JavaScript (ES6), 81 69 67 64 bajtów

Pobiera listę monet ci docelową kwotę aw składni curry (c)(a). Zwraca 0lub true.

c=>g=(a,m=1)=>c.map((c,i)=>x-=c*(m>>i&1),x=a)&&!x||x-a&&g(a,m+1)

Przypadki testowe

let f =

c=>g=(a,m=1)=>c.map((c,i)=>x-=c*(m>>i&1),x=a)&&!x||x-a&&g(a,m+1)

const pound = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000];

console.log(f(pound)(6))
console.log(f(pound)(15))
console.log(f(pound)(88))
console.log(f(pound)(512))
console.log(f(pound)(7003))

console.log(f(pound)(4))
console.log(f(pound)(209))
console.log(f(pound)(8889))
console.log(f(pound)(4242424242))

Haskell , 28 bajtów

Funkcja operatora (#)pobiera liczbę całkowitą i listę liczb całkowitych (lub, bardziej ogólnie, dowolny Traversablekontener liczb) i zwraca a Bool.

Użyj jako 6#[1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000].

c#l=elem c$sum<$>mapM(:[0])l

Wypróbuj online!

Jak to działa

• cjest pożądaną wartością i llistą wartości monet.
• mapM(:[0])lmapy (:[0])ciągu l, łącząc każdą wartość 0, a następnie tworzy iloczyn kartezjański, nadając list w którym każdy element jest albo jej odpowiednia wartość l, lub 0.
• sum<$>sumuje każdą kombinację i elem c$sprawdza, czy cznajduje się na wynikowej liście.

R, 88 83 bajtów

-5 bajtów dzięki @Jarko Dubbeldam

zwraca anonimową funkcję. Generuje wszystkie możliwe kombinacje monet (przy użyciu expand.gridpar T,F) i sprawdza, czy wartości są obecne. kto monety, ponieważ cjest zastrzeżonym słowem w R. Może sprawdzać wiele wartości jednocześnie.

function(k,v)v%in%apply(expand.grid(Map(function(x)!0:1,k)),1,function(x)sum(k[x]))

Wypróbuj online!

Japt , 7 bajtów

à mx èN

Wypróbuj online! Wyjścia 0dla fałszu, dodatnia liczba całkowita dla prawdy.

Wyjaśnienie

à mx èN
          // Implicit: U = input array, V = input integer, N = array of all inputs
à         // Take all combinations of U.
  mx      // Map each combination to its sum.
     è    // Count the number of items in the result which also exist in
      N   //   the array of inputs.
          // This returns 0 if no combination sums to V, a positive integer otherwise.
          // Implicit: output result of last expression

Python 3 , 52 bajty

5 bajtów dzięki ovs.

f=lambda c,n:c and f(c[1:],n-c[0])|f(c[1:],n)or n==0

Wypróbuj online!

Rubin , 39 bajtów

Zwraca nilwartość fałszowania i najmniejszą wartość monety na liście, która sprawia, że ​​liczba jest prawdziwa (wszystkie liczby są prawdziwe w Rubim).

f=->c,n{n!=0?c.find{|i|f[c-[i],n-i]}:1}

Uważaj jednak, że ten algorytm jest niezwykle powolny, ze O(C!)złożonością czasową, gdzie Cjest długość listy monet. W końcu się kończy, ale większość przypadków testowych przekroczy limit czasu nawet u większości tłumaczy internetowych f(UK_POUND, 5).

Oto 41-bajtowa wersja, która kończy się znacznie szybciej, dodając dodatkowy warunek zakończenia i znacznie trudniej jest przekroczyć limit czasu

f=->c,n{n>0?c.find{|i|f[c-[i],n-i]}:n==0}

Wypróbuj online!

Narzędzia Bash + GNU, 56 39

printf %$2s|egrep "^ {${1//,/\}? {}}?$"

Lista nazw wejściowych (nieposortowana) jest podawana jako lista oddzielona przecinkami. Lista wejściowa i wartość są podane jako parametry wiersza polecenia.

Dane wyjściowe podane w postaci kodu powrotu powłoki. Sprawdź echo $?po uruchomieniu skryptu. 0oznacza prawdę, 1oznacza fałsz.

Wypróbuj online .

• printf %$2swypisuje ciąg valuespacji
• "^ {${1//,/\}? {}}?$"jest rozszerzeniem powłoki, które rozszerza listę nazw do wyrażeń regularnych ^ {1}? {2}? {5}? {10}? ... $. Okazuje się, że egrepsilnik regex jest wystarczająco inteligentny, aby poprawnie się z tym dopasować, bez względu na kolejność nominałów
• egrep sprawdza, czy ciąg spacji pasuje do wyrażenia regularnego

C, 66 bajtów

m;v;f(n){for(m=1e5;m/=10;)for(v=5;n-=n<v*m?0:v*m,v/=2;);return!n;}

Zobacz, jak to działa tutaj .

C, 53 bajty

g(c,w,n)int*c;{for(;n-=n<c[--w]?0:c[w],w;);return!n;}

Ten wariant przyjmuje tablicę monet, która pokonuje cel tego problemu, ponieważ sprowadza się do zwykłego odejmowania.

Pierwszy argument to tablica monet, drugi to liczba monet, a trzeci to wartość.

C, 48 bajtów

g(c,n)int*c;{for(;n-=n<*c?0:*c,*++c;);return!n;}

Alternatywa dla poprzedniego wariantu. Zakłada, że ​​tablicę monet można odwrócić i zerować.

Pyth , 6 bajtów

/sMtyE

Zestaw testowy.

CJam , 18 17 bajtów

q~_,2\m*\f.*::+#)

Wypróbuj online!

Wyjaśnienie

q~                  e# Read and eval input.
  _,                e# Duplicate the money list and take its length.
    2\m*            e# Take the (length)th Cartesian power of [0 1].
        \f.*        e# Element-wise multiplication of each set of 0's and 1's with the money
                    e#   list. This is essentially the powerset, but with 0s instead of 
                    e#   missing elements.
            ::+     e# Sum each set.
               #    e# Find the index of the desired amount in the list. (-1 if not found)
                )   e# Increment. -1 => 0 (falsy), anything else => nonzero (truthy)

C (gcc) , 91 bajtów

i,j,c[]={1,2,5};f(n){for(i=1000;i;i/=10)for(j=2;j>=0;j--)n-=n<i*c[j]?0:i*c[j];return n==0;}

Wypróbuj online!

PHP, 70 bajtów

drukuje 1 za prawdę i nic za fałsz

<?foreach($_GET[1]as$v)$i-=$v*$r[]=($i=&$_GET[0])/$v^0;echo max($r)<2;

Wypróbuj online!

Oktawa, 39 bajtów

 @(L,n)any(cellfun(@sum,powerset(L))==n)

Anonimowa funkcja, która przyjmuje tablicę wartości monet jako pierwszy argument i docelową liczbę całkowitą jako drugi argument i zwraca wartość true lub false.

Wypróbuj online!

Mathematica, 42 bajty

ListQ@NumberDecompose[#,Sort[#2,Greater]]&

wkład

[15, {10,5}]