[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.
Коригирано.
[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
А на последния пример получаваш ли отговора, който е даден?
Да
S = 100
Coins = {50,20,20,20,20,20,10}
0: 10 + 20 + 20 + 50
1: 20 + 20 + 20 + 20 + 20
Това обаче е от следващата задача - сума с ограничен брой монети. На 4-та последният тест е
S = 100
Coins = {1,2,5,10,20,50,100}
Отговор: 4563
16 е отговорът, не е 18. Мисля че лесно може да се провери с лист и химикал :)
Ще задам въпроса си тук, за да не отварям нова тема. На четвърта задача съм тотален блокаж. Избрах следния подход - цикля през монетите и например когато сумата е 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
Ето моето решение:
http://www.heypasteit.com/clip/28LG
На C++ е но не би трябвало да представлява проблем, а и кода е малко.
Не съм сигурен къде точно ти е проблема, но пробвах с моето решение случая, който описа и сработи.
Най-лесният вариант, според мен, който съм го направил е да тръгнеш от най-голямата монета.
Да кажем, че имаш 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, като следващата рекурсия започваш или от него или от следваща монета, но никога назад.
Прегледах кода, но не ми е ясно как работи при неограничено количество от всяка монета. Доколкото разбирам, имаш краен брой монети, минаваш през всички, тестваш всички възможни суми и вземаш комбинациите, които покриват условието.