Софтуерно Инженерство
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 388 Точки

Ще задам въпроса си тук, за да не отварям нова тема. На четвърта задача съм тотален блокаж. Избрах следния подход - цикля през монетите и например когато сумата е 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 825 Точки

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

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 388 Точки

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

0
mihayloff14 avatar mihayloff14 825 Точки

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

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 289 Точки

Аз я реших итеративно:  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 832 Точки

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

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

@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