Escriba un programa que calcule si un valor monetario ingresado, como un entero, puede representarse mediante una combinación única de monedas y / o billetes, lo que significa que la misma moneda / billete no puede usarse más de una vez.

Su programa debe tomar un valor como entrada, y puede tomar una lista de valores de monedas / billetes ya sea a través de la entrada o del equivalente de una matriz de su idioma. La lista de monedas / billetes debería poder cambiar, así que asegúrese de que esté claro dónde está definido si está usando una constante.

Su programa debería generar cualquier valor de verdad / falsedad respectivamente.

Tenga en cuenta que no se requiere generar la lista de monedas / billetes que componen el valor .

EJEMPLO

Usando la libra esterlina, (£ 1.00 = 100 y £ 420.69 = 42069)

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

Lo siguiente dará como resultado verdadero:

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

Lo siguiente dará como resultado falso:

4
209
8889
4242424242
[ANYTHING ABOVE 8888]

DATOS ALTERNATIVOS DE PRUEBA (Dólar estadounidense)

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

¡Buena suerte!

Brachylog 2 (TIO Nexus), 2 bytes

⊇+

Pruébalo en línea!

Toma la lista de monedas ya sea a través de la entrada estándar o anteponiéndola al inicio del programa como una matriz literal (cualquiera de las dos funcionará, por lo que depende de usted lo que considere "más legítimo"; la primera está permitida por defecto Reglas PPCG, esta última específicamente permitida por la pregunta); y toma el valor para producir como un argumento de línea de comando.

Explicación

Este programa hace uso de detalles de implementación de la forma en que el contenedor de TIO Nexus para las funciones de Brachylog; específicamente, le permite dar un argumento de línea de comando para dar entrada a través de la Salida. (Esto no estaba previsto en el diseño original de Brachylog; sin embargo, los idiomas se definen por su implementación en PPCG, y si aparece una implementación que haga lo que necesito, por lo tanto, puedo aprovecharla). Eso significa que el programa se ve así:

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

Como programa completo, devuelve un valor booleano; true.si todas las afirmaciones en el programa pueden ser satisfechas simultáneamente, o false.si no pueden serlo.

(Un recordatorio, o para las personas que aún no lo saben: Brachylog 2 usa su propia codificación de caracteres en la que ⊇hay un solo byte de largo).

05AB1E , 4 bytes

æOså

Explicación:

æ      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.

Pruébalo en línea!

Mathematica, 25 bytes

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

Función pura que toma una matriz de valores de monedas como primer argumento y el entero objetivo como segundo argumento, y devuelve Trueo False.

Jalea, 6 bytes

ŒPS€e@

Pruébalo en línea!

-2 bytes gracias a Leaky Nun
-13 bytes gracias a Leaky Nun (larga historia)

Retina , 52 31 bytes

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

Pruébalo en línea! Toma datos como una lista de monedas y billetes separados por espacios, seguidos del valor deseado. Editar: ahorré 18 bytes gracias a @Kobi que depuró mi código. Explicación: Las dos primeras líneas simplemente se convierten de decimal a unario. La tercera línea captura la lista de monedas y billetes. La alternancia permite que el motor retroceda y elija no capturar monedas / billetes específicos. El grupo de equilibrio luego compara el valor con todos los sufijos de la lista de captura (innecesario pero más golfista).

Brachylog , 7 bytes

tT&h⊇+T

Pruébalo en línea!

Cómo funciona

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

Incluyendo la combinación, 9 bytes

tT&h⊇.+T∧

Pruébalo en línea!

Java (OpenJDK 8) , 125 bytes

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

Pruébalo en línea!

Prólogo (SWI) , 46 bytes

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

Pruébalo en línea!

Tenedor de mi respuesta Python .

JavaScript (ES6), 81 69 67 64 bytes

Toma la lista de monedas cy la cantidad objetivo aen sintaxis de curry (c)(a). Devoluciones 0o true.

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

Casos de prueba

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 bytes

La función de operador (#)toma un entero y una lista de enteros (o, más generalmente, cualquier Traversablecontenedor de números) y devuelve unBool .

Usar como 6#[1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000].

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

Pruébalo en línea!

Cómo funciona

• c es el valor deseado y l la lista de valores de monedas.
• mapM(:[0])lmapas (:[0])sobre l, el emparejamiento de cada valor con 0 y, a continuación construye el producto cartesiano, dando listas donde cada elemento es o bien su valor correspondiente en l, o 0.
• sum<$>suma cada combinación y elem c$comprueba si cestá en la lista resultante.

R, 88 83 bytes

-5 bytes gracias a @Jarko Dubbeldam

devuelve una función anónima Genera todas las combinaciones posibles de monedas (utilizando expand.gridpares de T,F) y comprueba si los valores están presentes. kes monedas ya que ces una palabra reservada en R. Puede verificar múltiples valores a la vez.

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

Pruébalo en línea!

Japt , 7 bytes

à mx èN

Pruébalo en línea!Salidas0 para falsedad, un entero positivo para verdad.

Explicación

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

5 bytes gracias a los ovs.

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

Pruébalo en línea!

Ruby , 39 bytes

Devuelve nilcomo el valor falso, y el valor de moneda más pequeño en la lista que compone el número como verdadero (todos los números son verdaderos en Ruby).

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

Sin embargo, tenga en cuenta que este algoritmo es increíblemente lento, con O(C!)complejidad de tiempo, donde Cestá la longitud de la lista de monedas. Eventualmente termina, pero la mayoría de los casos de prueba se agotarán en la mayoría de los intérpretes en línea, inclusof(UK_POUND, 5) .

Aquí hay una versión de 41 bytes que termina mucho más rápido al agregar una condición de finalización adicional, y es mucho más difícil de superar.

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

Pruébalo en línea!

Bash + utilidades GNU, 56 39

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

La lista de denominación de entrada (sin clasificar) se proporciona como una lista separada por comas. La lista de entrada y el valor se proporcionan como parámetros de línea de comandos.

Salida dada en forma de código de retorno de shell. Inspeccione con echo $?después de ejecutar el script. 0significa verdad, 1significa falsedad.

Pruébalo en línea .

• printf %$2sgenera una cadena de valueespacios
• "^ {${1//,/\}? {}}?$" es una expansión de shell que expande la lista de denominaciones a una expresión regular como ^ {1}? {2}? {5}? {10}? ... $ . Resulta que el egrepmotor regex es lo suficientemente inteligente como para coincidir correctamente con esto, independientemente del orden en que se encuentren las denominaciones
• egrep comprueba si la cadena de espacios coincide con la expresión regular

C, 66 bytes

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

Véalo funcionar aquí .

C, 53 bytes

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

Esta variante toma la matriz de monedas, lo que anula el propósito de este problema, porque se reduce a una simple resta.

El primer argumento es la matriz de monedas, el segundo es el recuento de monedas y el tercero es el valor.

C, 48 bytes

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

Una alternativa a la variante anterior. Se supone que la matriz de monedas se puede revertir y terminar con cero.

Pyth , 6 bytes

/sMtyE

Banco de pruebas.

CJam , 18 17 bytes

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

Pruébalo en línea!

Explicación

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 bytes

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

Pruébalo en línea!

PHP, 70 bytes

imprime 1 para verdadero y nada para falso

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

Pruébalo en línea!

Octava, 39 bytes

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

Una función anónima que toma una matriz de valores de monedas como el primer argumento y el entero de destino como el segundo argumento, y devuelve verdadero o falso.

Pruébalo en línea!

Mathematica, 42 bytes

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

entrada

[15, {10,5}]