Професионална програма
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 4486 Точки

Коригирано.

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

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

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

Това обаче е от следващата задача - сума с ограничен брой монети. На 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 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