@maksvolf96

Здравствуйте, нужен алгоритм подсчета количества возможных сумм элементов из множества Q, где B-требуемая сумма, например
множество M=(1,5,2);
M=30;
Другими словами нужно посчитать количество всевозможных "разложений" из 1,5,2 , чтобы получилось 30, не обязательно использовать каждый и элементов множества Q, например решение 1*30 тоже допустимо или 1*14+2*1 также допустимо
Пример:
N=30
M=(1,5,2)
Ответ 58.

В данном случае все несложно и можно решить простым перебором, но если обобщить задачу, например
для N<=60 и M<=500 , то уже стоит подумать и не решать простым перебором. Или все таки поместится в одну секунду? как вы считаете? Вот кстати само условие задачи, сразу стоило бы его предоставить:

Вася отошел от банкомата держа в руках свежую хрустящую купюру в N тугриков. Сегодня Вася твердо решил потратить все свои N тугриков, но придя в магазин он обнаружил, что там всего M товаров цены которых попарно различны. Сколько различных наборов товаров Вася может купить себе? Ограничение по времени 5 сек.
Входной файл: В первой строке числа N <= 60, M <= 500.
Во второй строке M чисел k1, k2, …, km – стоимости товаров.
Выходной файл: количество возможных наборов.
Примеры:
Вход:
30 3
1 5 2
Выход:
58

0

@Somebody

0

@maksvolf96

Somebody, не очень понятно как и почему это будет работать, а также что есть ответ.Не могли бы вы пояснить?

0

@Somebody

count[x] - количество разложений числа x.
count[x] = count[x - M[0]] + count[x - M[1]] + ... + count[x - M[...]]
Рекурсия, динамическое программирование...

0

@maksvolf96

То есть выутверждаете, что F(30)=F(30-1)+F(30-2)+F(30-5)?

Добавлено через 46 минут
Я понимаю, что решение динамическое, но в предложенном вами варианте можно найти пример, например из
вышеприведенного:
M=(1,2,5);
F(6)=5;
F(5)=4;
F(4)=3;
F(1)=1;
F(6)<>F(5)+F(4)+F(1);

0

@Somebody

Вот так тогда:
F(x, m) - количество разложений x с минимальным числом в разложении m.
F(x, m) = ∑ F(x − x_i, x_i), x_i ∈ M, x_i ⩾ m
F(6,1) = 5 = F(5,1) [{5, 2+2+2, 2+1+1+1, 1+1+1+1+1} + 1] + F(4,2) [{2+2} + 2] + F(1,5) [-]
F(5,1) = 4 = F(5,0) [5] + F(4,1) [{2+2, 2+1+1, 1+1+1+1} + 1] + F(3, 2) [-]
F(4,2) = 1 = F(2,2) [{2} + 2]
F(4,1) = 3 = F(3,1) [{2+1, 1+1+1} + 1] + F(2,2) [{2} + 2]
...

1

@Igor3D

Хорошо известна "задача о монетках". т.е. найти разложение на мин число заданных эл-тов. Думается разница только в том что нужно запоминать все предыдущие (а не только кратчайший)

0

@maksvolf96

Somebody, Спасибо большое, с 1 раза сдал, исходя из вашего алгоритма)

0