Loading...
Ivaka127 avatar Ivaka127 20 Точки

[Homework] Algorithms - Dynamic Programming

На третия тестови инпут има грешка.
Импутът не трябва да е
"7,17,45,91,11,32,102,33,6,3,6,8"
а "7,17,45,91,11,32,102,33,6,3"
С първия се получават 180 и 181, а с втория 173 и 174.

2
Структури от данни и алгоритми 14/10/2015 22:57:34
Hristo_Penchev avatar Hristo_Penchev 389 Точки

Ще задам въпроса си тук, за да не отварям нова тема. На четвърта задача съм тотален блокаж. Избрах следния подход - цикля през монетите и например когато сумата е 6 и съм на монета 1, смятам всички възможни комбинации за сума 5. После на монета 2 смятам всички възможни комбинации за сума 4 и т.н. до края на списъка с монети. Съответно 5 и 4 ги смятам рекурсивно по същия начин. Дъно на рекурсията ми е сума 0. Но се сблъсквам със следния проблем. Да речем търсим сума 3 и имаме монети от 1 и 2. Съответно първо от 3 вадим 1 и търсим комбинациите за 2. Те са {1, 1} и {2}. Съответно вадим комбинации {1, 1, 1} и {2, 1}. После търсим за 2 и рекурсивно за 3 - 2 = 1. Вадим комбинацията {1}, съответно става {1, 2}. Но това е същото като {2, 1). Как решавате този проблем? Разбира се, има си брутално дървеното решение, в което да пазя някъде комбинациите в сортиран вид и да проверявам дали има такава, но идеята е да намерим по-интелигентен вариант. Ето кода ми:

http://pastebin.com/C4qPmLFa

0
mihayloff14 avatar mihayloff14 824 Точки

Ето моето решение:

http://www.heypasteit.com/clip/28LG

На C++ е но не би трябвало да представлява проблем, а и кода е малко.

Не съм сигурен къде точно ти е проблема, но пробвах с моето решение случая, който описа и сработи.

0
Ivaka127 avatar Ivaka127 20 Точки

Най-лесният вариант, според мен, който съм го направил е да тръгнеш от най-голямата монета.
Да кажем, че имаш 13 с монети от 5, 2, 1. Тръгваш с петиците и я слагаш, следващат рекурсия я почваш със сумата -5 и пак с петици, когато стигнеш до следващата по стойност монета, всяка следваща рекурсия я почваш с нея, а не се връщаш на петиците.

private static void GetCombination(int target, int[] nums, List<int> temp, int startIndex)
{
    if (target == 0)
    {
        AddCombination(temp);
    }
    else if (target > 0)
    {
        for (var i = startIndex; i >= 0; i--)
        {
            int num = nums[i];
            target = target - num;
            if (target >= 0)
            {
                temp.Add(num);
                GetCombination(target, nums, temp, i);
                temp.RemoveAt(temp.Count - 1);
            }
            target = target + num;
        }
    }
}

В startIndex пазя до коя монета съм стигнал последно.
Според мен ключовото е започването от startIndex, като следващата рекурсия започваш или от него или от следваща монета, но никога назад.

0
Hristo_Penchev avatar Hristo_Penchev 389 Точки

Прегледах кода, но не ми е ясно как работи при неограничено количество от всяка монета. Доколкото разбирам, имаш краен брой монети, минаваш през всички, тестваш всички възможни суми и вземаш комбинациите, които покриват условието.

0
mihayloff14 avatar mihayloff14 824 Точки

Моето решение работи с неограничени монети, защото когато искам да генерирам следващата монета, не започвам от индекса на следващата монета, а от индекса на текущата.

FindSumElements(currentIndex + 1, index, sum - numbers[index]);

Това е (index) а не (index - 1)

0
21/10/2015 14:45:16
iliqnvidenov avatar iliqnvidenov 16 Точки

http://pastebin.com/rvDF3u7G Това е моето решение на тази задача, което също е рекурсивно. Моят въпрос обаче е, не трябва ли да измислим по-бързо решение от рекурсивното, за този тип проблеми.. аз си блъсках главата доста време и с 3та, и 4та, а пета въобще не успях да я реша.. Убеден съм, че ако реша подобна задача рекурсивно на изпита, ще ми изгърми за време в 80% от тестовете.. но някак така и не успявам да измисля решение с DP.. Според мен ще е хубаво да качват някъде и авторските решения на задачите от домашното, за да можем да свикнем с този тип мислене... междувременно ако някой може да ми хвърли решение на 5тa и на 3та задача, като 3та да не включва сортиране на числата, защото е много бавно.. Благодаря.

0
dim4o avatar dim4o 288 Точки

Аз я реших итеративно:  http://pastebin.com/GVXtfats

Със сигурност е възможно и още по-оптимално, но мисля, че това е достатъчно просто и оставих рекурсивния вариант да го направя по-нататък като упражнение. Просто се използва рекурентната връзка:

memo[row, col] = memo[row - 1, col] + memo[row, col - coins[row]]

 при пълненето на матрицата и търсеният резултат излиза най-долу вдясно - както при повечето задачи от този тип.

0
21/10/2015 18:34:54
nikola.m.nikolov avatar nikola.m.nikolov 830 Точки

Моето решение на 4-та задача, което дадох, не използва рекурсия и е използвано DP.

0
21/10/2015 18:35:46
dim4o avatar dim4o 288 Точки

@iliqnvidenov

Според мен проблема не идва от използването на рекурсия, а от това че използваш рекурентна връзка, при която е трудно да се приложи DP. Виж в добре познатата книга "Програмиране = ++Алгоритми" - там ги има решени тези задачи с рекурсия. Примерите са на C, но това предполагам няма да ти е проблем. Според мен обаче там обясненията са доста зле, въпреки че колекцията от алгоритми наистина е много добра. Едно пояснение или псевдокод от wikipedia често са ми по-полезни от написаното в тази книга. Но хората са различни - за теб написаното там може да се окаже много по-полезно.

Ако си добре с Индийския това също може да ти е полезно за рекурсивния вариант: https://www.youtube.com/watch?v=Kf_M7RdHr1M&list=PLtE7QNA19r-ZKVXrXBjqe-pkpjsnklxjh&index=10

1
21/10/2015 20:56:21
iliqnvidenov avatar iliqnvidenov 16 Точки

Всъщност успях да измисля някакъв вариант на тази задача с ползване на DP.. проблема явно е, че за пръв път виждам подобен вид начин на мислене и ми се струва малко като магия.. блалала.. но съм убеден, че с малко повече труд ще станат нещата.. БЛАГОДАРЯ за линковете. Просто в това домашно се старах да не използвам рекурсия, а само DP, което явно не ми е все още по силите. :D

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