15.05.2016, 01:16
|
|
I am Student
|
|
Регистрация: 17.12.2011
Сообщений: 4,415
|
|
Алгоритм размена монет
Нужно написать прогу которая считает сколькими способами можно разменяь какуе то квоту. Есть квота, есть монеты для размена и их количество, сделать нужно через backtracking .
то что я придумал выглядит примерно так, например есть
10(стоимсть монеты) 5 (количество)
7 3
8 3
1 7
с этого строю матрицу
var values = [
[ 0, 10, 20, 30, 40, 50 ],
[0, 7, 14, 21],
[0, 8, 16, 24],
[0, 1, 2, 3, 4, 5, 6, 7]
];
выглядит это примерно так
var count = (values, y, coinValue) => {
if(y >= values.length)
return 0;
var res = 0;
for(var i = 0; i < values.length; i++) {
var v = coinValue - values[y][i];
if(v === 0)
res++
else if( v > 0) {
res+= count(values, y + 1, v);
}
else {
break;
}
}
return res;
}
var values = [
[ 0, 10, 20, 30, 40, 50 ],
[0, 7, 14, 21],
[0, 8, 16, 24],
[0, 1, 2, 3, 4, 5, 6, 7]
];
var coinChangeValue = 55;
var res = 0;
for (var i = 0; i < values[0].length; i++) {
var val = coinChangeValue - values[0][i];
res += count(values, 1, val);
}
console.log(res);
Мне нужно как то оптимизировать сам алгоритм, потому что он слишком долго работает для больших чисел, гугли разные варианты, но как то не особо идет.
Может ктото подкинет идейку
какие то мелкие оптимизации не имею смысла код переписан с С++, я не могу оригинальный код вкинуть потому что система поиска плагиата меня отмыеет потом)) (это для универа).
__________________
Цитата:
|
Если ограничения и условия описываются как "коробка", то хитрость в том что бы найти именно коробку... Не думайте о чем то глобальном - найдите коробку.
|
|
|
15.05.2016, 02:18
|
|
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,120
|
|
cyber,
<script>
function combinator(matrix){
return matrix.reduceRight(function(combination, x){
var result = [];
x.forEach(function(a){
combination.forEach(function(b){
result.push( [ a ].concat( b ) );
});
});
return result;
});
};
var arr = combinator([ [ 0, 10, 20, 30, 40, 50 ],[0, 7, 14, 21],[0, 8, 16, 24],[0, 1, 2, 3, 4, 5, 6, 7]] );
arr = arr.filter(function(a) {
return 55 == a.reduce(function(a,b) {
return a + b
})
})
document.write(
arr.join("<br>")+ "<br>Всего вариантов : " + arr.length
);
</script>
|
|
15.05.2016, 02:44
|
|
I am Student
|
|
Регистрация: 17.12.2011
Сообщений: 4,415
|
|
рони, хм, а это идея, записать все возможные комбинации, а потом отфильровать, попробую, но мне кажется лимит по памяти не пройдет)
Спасибо за вариант, сейчас перепишу на С++))
__________________
Цитата:
|
Если ограничения и условия описываются как "коробка", то хитрость в том что бы найти именно коробку... Не думайте о чем то глобальном - найдите коробку.
|
|
|
15.05.2016, 12:59
|
|
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,120
|
|
cyber,
не знаю что выгоднее проверить все варианты один раз, или отсеивать по мере создания варианта, тогда вариантов в целом может быть меньше, но проверок больше каждого до 4 (в данном случае)
Последний раз редактировалось рони, 15.05.2016 в 13:02.
|
|
15.05.2016, 13:38
|
|
I am Student
|
|
Регистрация: 17.12.2011
Сообщений: 4,415
|
|
рони, не прошло, в 2 раза превысило лимит памяти
__________________
Цитата:
|
Если ограничения и условия описываются как "коробка", то хитрость в том что бы найти именно коробку... Не думайте о чем то глобальном - найдите коробку.
|
|
|
15.05.2016, 14:48
|
|
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,120
|
|
cyber,
тогда строить дерево ветка больше лимита отрезаем , ветка равна лимиту отрезаем в результат, меньше лимита оставляем и наращиваем.
|
|
15.05.2016, 14:52
|
|
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,120
|
|
cyber,
количество всех вариантов известно заранее 6 * 4 * 4 * 8 ... и не хранить все варианты а только верные результаты и четыре индекса.
|
|
15.05.2016, 15:09
|
|
I am Student
|
|
Регистрация: 17.12.2011
Сообщений: 4,415
|
|
рони, по сути больше проблема с временем работы чем с памятью, по сути при рекурсии я и так отбрасываю лишние и дальше не иду. Но еще по страдаю если не заработает то сделаю деревом, может так получится
__________________
Цитата:
|
Если ограничения и условия описываются как "коробка", то хитрость в том что бы найти именно коробку... Не думайте о чем то глобальном - найдите коробку.
|
|
|
15.05.2016, 15:17
|
|
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,120
|
|
cyber,
рекурсия кушает память как известно. может проще генерировать последовательно по одному и проверять подошёл не подошёл (это без оптимизации) ... 4 вложенных for c continue -- самый оптимальный вариант(для данного случая) ... понятно что нужен универсальный вариант.
|
|
15.05.2016, 15:41
|
|
I am Student
|
|
Регистрация: 17.12.2011
Сообщений: 4,415
|
|
Сообщение от рони
|
рекурсия кушает память как известно
|
да, я знаю, та версия алгоритма что у меня есть не проходит по времени по памяти норм, попробую еще раз на форах, если нет то перехожу к деревьям, хотя я реально не пойму как у некоторых одногрупников это заработало через рекурсию...
__________________
Цитата:
|
Если ограничения и условия описываются как "коробка", то хитрость в том что бы найти именно коробку... Не думайте о чем то глобальном - найдите коробку.
|
|
|
|
|