У меня в кармане 15 долларов. Точно так же я нахожусь в магазине, который не дает сдачи. Во время просмотра я замечаю предмет, который стоит 10 долларов (включая налог). Могу ли я купить этот товар без потери денег?

В этом случае ответ - да. Независимо от того, как разделены мои 15 долларов (одна 10 и одна 5, или три 5, или что-то еще), у меня всегда будет именно то, что нужно 10 долларов.

В качестве второго примера, у меня в кармане 0,16 доллара. Какие другие суммы денег я должен быть в состоянии заплатить точно?

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

Что если у меня в кармане 0,27 доллара?

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

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

Твое задание

Напишите самую короткую программу (или именованную функцию), которая принимает A) целую сумму денег и B) список возможных номиналов в качестве входных данных и выводит список сумм денег, для которых я должен иметь идеальное изменение. Ввод может быть либо STDIN, либо аргументами для программы или функции. Я не собираюсь быть очень строгим при форматировании ввода; это может соответствовать тому, как ваш язык форматирует массивы.

Возможно, более подробное объяснение

У меня в кармане определенная сумма денег, которая формируется из набора возможных демонстраций валюты. Если у меня есть 8 долларов, и я знаю, что возможными номиналами являются 2 и 3 доллара, то у меня в кармане будет так много разных комбинаций банкнот. Это 2+2+2+2и есть 3+3+2. Чтобы иметь возможность производить точное количество денег, я должен иметь возможность производить это количество, используя только те счета, которые у меня в кармане. Если бы у меня было четыре двойки, я мог бы произвести 2, 4, 6, or 8. Если бы у меня было два 3 и 2, я мог бы произвести. 2, 3, 5, 6, or 8Так как я не знаю, какую из этих комбинаций я на самом деле имею в своем кармане, мой окончательный ответ сводится к 2, 6, 8. Это те значения, которые я знаю, я мог бы получить из своего кармана, учитывая общую сумму и возможные номиналы.

Вычисленный вручную пример ввода / вывода

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

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}

(Спасибо @Nabb за советы)

Вот плохое решение для гольфа, чтобы начать все сначала. Call with g(16, [1, 5, 10, 25])- output - это набор с соответствующими номиналами.

Подход прост и разбит на два этапа:

• fрассматривает все способы достижения nс деноминациями D(например [1, 5, 10]), и для каждого из них вырабатываются все суммы, которые могут быть сделаны с этими деноминациями (например set([0, 1, 5, 6, 10, 11, 15, 16])).
• gвычисляет пересечения результатов f, а затем удаляет 0 для окончательного ответа.

Программа хорошо решает случаи 1-5 и 7, переполняет стек на 6 и берет навсегда на 8.

Если решения не существует (например g(7, [2, 4, 6])), программа возвращает пустой набор. Если в таком случае разрешено выдавать ошибку, то здесь короче g:

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

JavaScript (ES6) 162 203 207

Изменить Изменен способ пересечения наборов результатов в массиве r. Немного быстрее, но алгоритм все еще воняет.

Более подробное объяснение будет следовать.
Коротко: c - рекурсивная функция, которая перечисляет все возможные подразделения. k - рекурсивная функция, которая перечисляет все возможные суммы без повторений. Любой новый набор результатов, найденный с помощью функции k, сравнивается с предыдущим найденным набором, сохраняются только общие результаты.

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

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
}

Тест в консоли Firefox / FireBug

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

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

(время 84 мсек)

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

[1, 2, 25, 26, 27]

(время 147252 мсек, поэтому не ооочень быстро)

Wolfram Methematica, 104 байта

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

Ungolfed (читать с конца):

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