Loading...
a_rusenov avatar a_rusenov 1103 Точки

Наблюдението е следното:

Имаме монетите { 1, 2, 3 } и трябва да намерим всички начини (комбинации) да получим сумата S = 4. Ако махнем монетата 3, проблемът остава същият - с по-малък брой монети. Да примем, че знаем решението с монетите { 1, 2 } - 3 начина. Как това ни помага, когато добавим 3 към възможните монети? 

При всяко положение намерените начини поне ще се запазят. Добавяйки монети, решението може само да се разшири. Кога се разширява? В два случая:

  • Ако монетата е равна на сумата която търсим (напр. при S = 3, { 1, 2, 3 }, с 3 ще имаме още 1 начин да получим 3).
  • Ако съществуват вече начини да получим сумата - монетата. (напр. при S = 4, { 1, 2, 3 }, с 3 ще имаме също толкова начини да получим 4 колкото досега + начините да получим 1 (към които ще добавим 3, за да стане сумата 4).

И тука вече можем да си изведем следната рекурентна зависимост:

начините да получим 4 с { 1, 2, 3 } = начините да получим 4 с { 1, 2 } + начините да получим (4 - 3) с { 1, 2, 3 }

По-точно: Combinations(c, S) = Combinations(c - 1, S) + Combinations(c, S - coins[c]), където c е индексът на текущата монета, а S - търсената сума.

С bottom-up подход, много лесно може да си го изведем в таблица (редовете са монетите, колоните са сумите):

    0 1 2 3 4   
1  0 1 1 1 1
2  0 1 2 2 3
3  0 1 2 3 4

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

Помислете дали цялата таблица ни е необходима - можем ли да спестим памет? :)

4
21/04/2016 14:08:24
psdimitrov avatar psdimitrov 75 Точки

Здравей Наско,

И аз реших задачата по подобен начин с малка разлика, че когато търсената сума е 0, в таблицата попълвам 1(Броят начини да получиш сума равна на 0 е един, когато не използваш нито една монета). Така не се налага допълнително да се проверява дали сумата е равна на монетата, защото ако е така, то Combinations(c, S - coins[c]) става Combinations(c, 0), което е 1.

А относно пестенето на памет, от рекурентната зависимост се вижда, че се обръщаме към предходния ред, така че може вместо цяла таблица да пазим само един ред от нея. Аз съм ползвал едномерен масив.

Ето го моето решение: http://pastebin.com/i70hRmYB

3
25/04/2016 14:44:47
a_rusenov avatar a_rusenov 1103 Точки

Браво, не се бях усетил за нулата. :)

0
25/04/2016 20:33:22
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.