Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
maksvolf96
3 / 3 / 2
Регистрация: 18.05.2014
Сообщений: 203
1

Алгоритм подсчета количества сумм из множества

08.11.2014, 17:27. Просмотров 805. Ответов 7
Метки нет (Все метки)

Здравствуйте, нужен алгоритм подсчета количества возможных сумм элементов из множества 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
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.11.2014, 17:27
Ответы с готовыми решениями:

Алгоритм для подсчета количества инверсий
Как построить алгоритм, который для перестановки чисел(любой) будет считать общее количество...

Нахождение в строках матрицы отрицательных (<0) элементов, подсчета их количества и сумм
Напишите пожалуйста код с использованием процедур и функций: Вводится матрица MT (n,m) с...

Алгоритм для подсчета количества элементов в дереве
Здравствуйте! Помогите придумать алгоритм для подсчета элементов в дереве. Например нужно...

Быстрый алгоритм для подсчета количества делителей числа
Быстрый алгоритм для подсчета количества делителей натурального числа 1 &lt;= x &lt;= 1018. Помогите...

Опишите алгоритм подсчета максимального количества подряд идущих элементов
Опишите алгоритм подсчета максимального количества подряд идущих элементов, каждый из которых...

7
Somebody
3103 / 1624 / 251
Регистрация: 03.12.2007
Сообщений: 4,223
Завершенные тесты: 3
08.11.2014, 17:39 2
Код
for i in [0, N)
  for j in M
    count[i + j] := count[i + j] + 1
0
maksvolf96
3 / 3 / 2
Регистрация: 18.05.2014
Сообщений: 203
08.11.2014, 17:56  [ТС] 3
Somebody, не очень понятно как и почему это будет работать, а также что есть ответ.Не могли бы вы пояснить?
0
Somebody
3103 / 1624 / 251
Регистрация: 03.12.2007
Сообщений: 4,223
Завершенные тесты: 3
08.11.2014, 18:16 4
count[x] - количество разложений числа x.
count[x] = count[x - M[0]] + count[x - M[1]] + ... + count[x - M[...]]
Рекурсия, динамическое программирование...
0
08.11.2014, 18:16
maksvolf96
3 / 3 / 2
Регистрация: 18.05.2014
Сообщений: 203
08.11.2014, 23:49  [ТС] 5
То есть выутверждаете, что 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
3103 / 1624 / 251
Регистрация: 03.12.2007
Сообщений: 4,223
Завершенные тесты: 3
09.11.2014, 12:30 6
Вот так тогда:
F(x, m) - количество разложений x с минимальным числом в разложении m.
F(x, m) = ∑ F(x − xi, xi), xi ∈ M, xi ⩾ 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
1229 / 596 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
09.11.2014, 13:19 7
Хорошо известна "задача о монетках". т.е. найти разложение на мин число заданных эл-тов. Думается разница только в том что нужно запоминать все предыдущие (а не только кратчайший)
0
maksvolf96
3 / 3 / 2
Регистрация: 18.05.2014
Сообщений: 203
10.02.2015, 17:33  [ТС] 8
Somebody, Спасибо большое, с 1 раза сдал, исходя из вашего алгоритма)
0
10.02.2015, 17:33
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.02.2015, 17:33

Алгоритм подсчета количества чисел, которые делятся нацело на сумму своих цифр
Добрый день. Вот разобраться не могу как реализовать подсчет количества чисел, которые делятся...

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

Массив: Составьте алгоритм для подсчета количества дней, имеющих наибольшую температуру.
Текст задачи: &quot;Составьте алгоритм для подсчета количества дней, имеющих наибольшую температуру (за...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.