Mam 15 $ w kieszeni. Podobnie jestem w sklepie, który nie daje zmian. Podczas przeglądania zauważam przedmiot, który kosztuje 10 USD (zawiera podatek). Czy mogę kupić ten przedmiot bez utraty pieniędzy?

W takim przypadku odpowiedź brzmi „tak”. Bez względu na to, jak podzielę moje 15 $ (jedno 10 i jedno 5, lub trzy 5, lub coś innego), zawsze będę potrzebował dokładnie 10 $.

Jako drugi przykład mam 0,16 $ w kieszeni. Jakie inne kwoty muszę dokładnie zapłacić?

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

Co jeśli mam 0,27 $ w kieszeni?

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

W powyższym przypadku było tylko kilka pieniędzy, na które zawsze miałbym idealną zmianę.

Twoje zadanie

Napisz najkrótszy program (lub nazwaną funkcję), który bierze A) całkowitą kwotę pieniędzy i B) listę możliwych nominałów jako dane wejściowe i wyświetla listę kwot pieniędzy, na które muszę mieć doskonałą zmianę. Dane wejściowe mogą być STDIN lub argumentami programu lub funkcji. Nie będę zbyt surowy w zakresie formatowania danych wejściowych; może pasować do sposobu, w jaki tablice formatują Twój język.

Być może bardziej szczegółowe wyjaśnienie

Mam w kieszeni pewną ilość pieniędzy, która powstaje z zestawu możliwych demonstracji waluty. Jeśli mam 8 USD i wiem, że możliwymi nominałami są 2 i 3 USD, to w mojej kieszeni jest tyle różnych kombinacji rachunków. To są 2+2+2+2i 3+3+2. Aby móc wyprodukować dokładną ilość pieniędzy, muszę być w stanie wyprodukować tę ilość, korzystając tylko z rachunków, które mam w kieszeni. Gdybym miał cztery 2, mógłbym wyprodukować 2, 4, 6, or 8. Gdybym miał dwie 3 i 2, mógłbym wyprodukować 2, 3, 5, 6, or 8Ponieważ nie wiem, które z tych kombinacji faktycznie mam w kieszeni, moja ostateczna odpowiedź jest ograniczona do 2, 6, 8. Są to wartości, które wiem, że mógłbym wytworzyć z kieszeni, biorąc pod uwagę całkowitą kwotę i możliwe nominały.

Ręcznie obliczany przykład I / O

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 bajtów

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}

(Podziękowania dla @Nabb za wskazówki)

Oto na razie kiepskie rozwiązanie na początek. Połączenie z g(16, [1, 5, 10, 25])- wyjściem jest zbiorem o odpowiednich nominałach.

Podejście jest proste i dzieli się na dwa etapy:

• fanalizuje wszystkie sposoby dotarcia ndo nominałów D(np. [1, 5, 10]) i dla każdego z nich oblicza wszystkie kwoty, które można uzyskać za pomocą tych nominałów (np set([0, 1, 5, 6, 10, 11, 15, 16]).).
• goblicza przecięcia wyników f, a następnie usuwa 0 dla ostatecznej odpowiedzi.

Program rozwiązuje przypadki 1-5 i 7 grzywny, przepełnienie stosu na 6 i trwa wiecznie na 8.

Jeśli nie ma rozwiązania (np. g(7, [2, 4, 6])), Program zwraca pusty zestaw. Jeśli w takim przypadku dopuszcza się błąd, jest to krótsze g:

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

JavaScript (ES6) 162 203 207

Edytuj Zmieniono sposób przecinania zestawów wyników w tablicy r. Trochę szybciej, ale algorytm wciąż śmierdzi.

Bardziej szczegółowe wyjaśnienie nastąpi.
W skrócie: c jest funkcją rekurencyjną, która wylicza wszystkie możliwe poddziały. k jest funkcją rekurencyjną, która wylicza wszystkie możliwe sumy bez powtórzeń. Każdy nowy zestaw wyników znaleziony za pomocą funkcji k jest porównywany z poprzednim znalezionym zestawem, zachowane są tylko wspólne wyniki.

Dlaczego jest taki wolny? Konieczność zarządzania docelową sumą, powiedzmy, 1500 i pojedynczą wartością o wartości 1, wyliczenie wszystkich możliwych kwot nie jest dobrym pomysłem.

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

Nie golfił

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
}

Przetestuj w konsoli Firefox / FireBug

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

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

(czas 84 ms)

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

[1, 2, 25, 26, 27]

(czas 147252 ms, więc nie tak szybko)

Wolfram Methematica, 104 bajty

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

Niegolfowany (czytany od końca):

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
                ]&