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
Filkolev avatar Filkolev 4482 Точки

Коригирано.

1
Ivaka127 avatar Ivaka127 20 Точки

[Homework] Algorithms - Dynamic Programming - Задача 4. Representing a Sum with Unlimited Amount of Coins

Третият тестови импут
S = 13
Coins = {1,2,5,10}
Резултат: 18

Аз го изкарвам 16.

0: 10 + 2 + 1
1: 10 + 1 + 1 + 1
2: 5 + 5 + 2 + 1
3: 5 + 5 + 1 + 1 + 1
4: 5 + 2 + 2 + 2 + 2
5: 5 + 2 + 2 + 2 + 1 + 1
6: 5 + 2 + 2 + 1 + 1 + 1 + 1
7: 5 + 2 + 1 + 1 + 1 + 1 + 1 + 1
8: 5 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
9: 2 + 2 + 2 + 2 + 2 + 2 + 1
10: 2 + 2 + 2 + 2 + 2 + 1 + 1 + 1
11: 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1
12: 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1
13: 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
14: 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
15: 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

 

0
Filkolev avatar Filkolev 4482 Точки

А на последния пример получаваш ли отговора, който е даден?

0
Ivaka127 avatar Ivaka127 20 Точки

Да

S = 100
Coins = {50,20,20,20,20,20,10}

 

0: 10 + 20 + 20 + 50
1: 20 + 20 + 20 + 20 + 20

 

0
15/10/2015 09:06:09
Filkolev avatar Filkolev 4482 Точки

Това обаче е от следващата задача - сума с ограничен брой монети. На 4-та последният тест е 

S = 100

Coins = {1,2,5,10,20,50,100}

Отговор: 4563

0
moholovka avatar moholovka 169 Точки

16 е отговорът, не е 18. Мисля че лесно може да се провери с лист и химикал :) 

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