Eu tenho 15 dólares no bolso. Da mesma forma, estou em uma loja que não dá troco. Ao navegar, localizo um item que custa US $ 10 (impostos incluídos). Posso comprar esse item sem perder dinheiro?

Nesse caso, a resposta é sim. Não importa como meus US $ 15 sejam divididos (um 10 e um 5, ou três 5s, ou outra coisa), sempre terei exatamente os US $ 10 necessários.

Como segundo exemplo, tenho $ 0,16 no bolso. Que outras quantias de dinheiro devo pagar exatamente?

Possible Divisions:
0.01, 0.05, 0.10
0.01, 0.05 x 3
0.01 x 16
Guaranteed Exact Change:
0.01, 0.05, 0.06, 0.10, 0.11, 0.15, 0.16

E se eu tiver US $ 0,27 no bolso?

Possible Divisions:
0.01 x 2, 0.25
0.01 x 2, 0.05, 0.10 x 2
0.01 x 2, 0.05 x 3, 0.10
0.01 x 2, 0.05 x 5
0.01 x 27
Guaranteed Exact Change:
0.01, 0.02, 0.25, 0.26, 0.27

No caso acima, havia apenas algumas quantias de dinheiro pelas quais eu sempre teria troco perfeito.

Sua tarefa

Escreva o programa mais curto (ou função nomeada) que leva A) uma quantidade inteira de dinheiro e B) uma lista de denominações possíveis como entrada e gera uma lista das quantias de dinheiro pelas quais devo ter uma mudança perfeita. A entrada pode ser STDIN ou argumentos para o programa ou função. Eu não vou ser super rigoroso na formatação de entrada; pode corresponder à forma como o seu idioma formata as matrizes.

Talvez uma explicação mais detalhada

Eu tenho uma certa quantia de dinheiro no meu bolso, formada a partir de um conjunto de possíveis demonstrações de moeda. Se eu tenho US $ 8 e sei que as denominações possíveis são US $ 2 e US $ 3, há apenas tantas combinações diferentes de notas que poderiam estar no meu bolso. Estes são 2+2+2+2e 3+3+2. Para poder produzir uma quantia exata de dinheiro, preciso produzir essa quantidade usando apenas as notas que estão no meu bolso. Se eu tivesse quatro 2s, eu poderia produzir 2, 4, 6, or 8. Se eu tivesse dois 3 e um 2, eu poderia produzir. 2, 3, 5, 6, or 8Como não sei qual dessas combinações realmente tenho no bolso, minha resposta final é reduzida para 2, 6, 8. Esses são os valores que sei que poderia produzir do meu bolso, considerando a quantidade total e as possíveis denominações.

Exemplo de E / S calculado manualmente

7 [3, 4]
3, 4, 7        //only one possible division into 3 + 4

7 [3, 2]
2, 3, 4, 5, 7  //the only division is 3 + 2 + 2

6 [2, 3, 4]
6     //divisions are 2+2+2, 3+3, 2+4 

16 [1, 5, 10, 25]          //this represents one of the examples above
1, 5, 6, 10, 11, 15, 16

27 [1, 5, 10, 25]          //another example from above
1, 2, 25, 26, 27

1500 [1, 5, 10, 25, 100, 500, 1000, 2000]
500, 1000, 1500

600 [100, 500, 1000, 2000]
100, 500, 600

600 [200, 1, 5, 10, 25, 100, 500, 1000, 2000]
600

Python 2, 200 197 193 140 bytes

f=lambda n,D,S={0}:sum([f(n-x,D,S|{x+y for y in S})for x in D],[])if n>0else[S]*-~n
g=lambda*a:(f(*a)and reduce(set.__and__,f(*a))or{0})-{0}

(Obrigado a @Nabb por dicas)

Aqui está uma solução mal preparada para começar agora. Chamada com g(16, [1, 5, 10, 25])- saída é um conjunto com as denominações relevantes.

A abordagem é direta e é dividida em duas etapas:

• fanalisa todas as maneiras de alcançar as ndenominações D(por exemplo [1, 5, 10]) e, para cada uma, calcula todas as quantias que podem ser feitas com essas denominações (por exemplo set([0, 1, 5, 6, 10, 11, 15, 16])).
• gcalcula as interseções dos resultados de fe remove 0 para a resposta final.

O programa resolve os casos 1-5 e 7, multa, transborda em 6 e leva para sempre em 8.

Se não houver solução (por exemplo g(7, [2, 4, 6])), o programa retornará um conjunto vazio. Se for permitido que um erro seja gerado para esse caso, eis uma breve g:

g=lambda*a:reduce(set.__and__,f(*a))-{0}

JavaScript (ES6) 162 203 207

Editar Alterada a maneira de cruzar conjuntos de resultados na matriz r. Um pouco mais rápido, mas o algoritmo ainda fede.

Uma explicação mais detalhada se seguirá.
Resumidamente: c é uma função recursiva que enumera todas as subdivisões possíveis. k é uma função recursiva que enumera todas as somas possíveis sem repetições. Qualquer novo conjunto de resultados encontrado com a função k é comparado com o conjunto anterior encontrado, apenas os resultados comuns são mantidos.

Por que é tão lento? Ter que gerenciar um total-alvo de, digamos, 1500 e um único valor 1, enumerar todas as somas possíveis não é uma boa idéia.

F=(s,d,r,
  c=(s,i,t=[],v,k=(i,s,v)=>{for(;v=t[i++];)k(i,s+v);o[s]=s})=>
  {for(s||(i=k(o=[],0),r=(r||o).filter(v=>o[v]));v=d[i];++i)s<v||c(s-v,i,[...t,v])}
)=>c(s,0)||r

Ungolfed

F=(s,d)=>{
  var r
  var c=(s,i,t=[])=>
  {
    var o=[],v
    var k=(i,s)=> // find all sums for the current list t, set a flag in the o array
    {
      var v
      for(;v=t[i++];)k(i,s+v)
      o[s]=s
    }

    if (s==0) {
      k(0,0)
      if (r)
        r = r.filter(v=>o[v]) // after first loop, intersect with current
      else
        r = o.filter(v=>v) // first loop, keep all results
    } 
    else
      for(;v=d[i];++i)
      { 
        if (s >= v) 
          c(s-v, i, t.concat(v))
      }
  }
  c(s,0) // enumerate all possible set of pieces
  return r
}

Teste no console Firefox / FireBug

F(16,[1,5,10,25])

[1, 5, 6, 10, 11, 15, 16]

(tempo 84 ms)

F(27, [1, 5, 10, 25]) 

[1, 2, 25, 26, 27]

(tempo 147252 ms, por isso não tão rápido)

Wolfram Methematica, 104 bytes

Rest@*Intersection@@Map[Total]/@Subsets/@Union[Sort/@IntegerPartitions[#,#,PadLeft[{},Length[#2]#,#2]]]&

Ungolfed (lido do final):

Rest@* // Removing 0
  Intersection@@   // Intersecting all totals
     Map[Total]/@  // Counting total of each subset
        Subsets/@  // Getting all the subsets of each partition
           Union[  // Removing duplicates 
              Sort/@ // Sorting each partition (to remove duplicates next)
                 IntegerPartitions[#,#,PadLeft[{},Length[#2]#,#2]] // Getting all Integer partitions
                ]&