Алгоритм размена монет
 

Нужно написать прогу которая считает сколькими способами можно разменяь какуе то квоту. Есть квота, есть монеты для размена и их количество, сделать нужно через 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);

Мне нужно как то оптимизировать сам алгоритм, потому что он слишком долго работает для больших чисел, гугли разные варианты, но как то не особо идет.
Может ктото подкинет идейку

какие то мелкие оптимизации не имею смысла код переписан с С++, я не могу оригинальный код вкинуть потому что система поиска плагиата меня отмыеет потом)) (это для универа).

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>

рони, хм, а это идея, записать все возможные комбинации, а потом отфильровать, попробую, но мне кажется лимит по памяти не пройдет)
Спасибо за вариант, сейчас перепишу на С++))

cyber,
не знаю что выгоднее проверить все варианты один раз, или отсеивать по мере создания варианта, тогда вариантов в целом может быть меньше, но проверок больше каждого до 4 (в данном случае)

рони, не прошло, в 2 раза превысило лимит памяти

cyber,
тогда строить дерево ветка больше лимита отрезаем , ветка равна лимиту отрезаем в результат, меньше лимита оставляем и наращиваем.

cyber,
количество всех вариантов известно заранее 6 * 4 * 4 * 8 ... и не хранить все варианты а только верные результаты и четыре индекса.

рони, по сути больше проблема с временем работы чем с памятью, по сути при рекурсии я и так отбрасываю лишние и дальше не иду. Но еще по страдаю если не заработает то сделаю деревом, может так получится

cyber,
рекурсия кушает память как известно. может проще генерировать последовательно по одному и проверять подошёл не подошёл (это без оптимизации) ... 4 вложенных for c continue -- самый оптимальный вариант(для данного случая) ... понятно что нужен универсальный вариант.

да, я знаю, та версия алгоритма что у меня есть не проходит по времени по памяти норм, попробую еще раз на форах, если нет то перехожу к деревьям, хотя я реально не пойму как у некоторых одногрупников это заработало через рекурсию...

cyber,
всего вариантов 768 за счёт оптимизации (continue) получилось 488 , а необходимые варианты были созданы только 1 раз (всего 13).

<script>
var num = [10, 7, 8, 1],
    res = [],
    limit = 55,
    a, b, c, e;
for (var i = 0; i <= 5; i++) {
    a = i * num[0];
    if (a > limit) continue;
    for (var k = 0; k <= 3; k++) {
        b = k * num[1];
        if (a + b > limit) continue;
        for (var n = 0; n <= 3; n++) {
            c = n * num[2];
            if (a + b + c > limit) continue;
            for (var d = 0; d <= 7; d++) {
                e = d * num[3];
                if (a + b + c + e == limit) res.push([a, b, c, e])
            }
        }
    }
};
document.write(
  res.join("<br>")+ "<br>Всего вариантов : " + res.length
);
</script>

Prolog использует поиск с возвратом.
cyber, ты бы открыл википедию и почитал, что такое поиск с возвратом. Я даже не понимаю, о каком поиске с возвратом может идти речь, если у вас нет дерева :)
Поиск с возвратом, это практически тоже самое, что и поиск в глубину, который, как и другие методы неинформированого поиска реализован (из коробки) в моем рекурсивном итераторе, http://javascript.ru/forum/project/5...-iterator.html :)

Вот тебе пример без дерева https://en.wikipedia.org/wiki/Sudoku...s#Backtracking
Проще говоря, это тупо перебор всех возможных вариантов, с нужными ифками на отброс лишних вариантов

рони, спасибо, ты быстрый, я только начал писать))
П.с а вообще я чет заигрался с рекурсией и костылями что не попробовал на форах
П.с.с я не знаю какие у меня буду входные данные, то что я дал это данные которые я вручную проверил и на них тестирую))

похоже, что понятие графа пространства состояний тебе не знакомо. Твоя ссылка как раз о нем.

nerv_, ты ведешь к тому что мне нужно дерево или граф?)

Но посути получается, что при рекурсии оно входит в своеобразное дерево и углубляется пока сумма меньше квоты

я пытаюсь сказать, что поиск с возвратом подразумевает наличие дерева/графа состояний, который (граф), зачастую, формируется на лету (on the fly). По крайней мере пятнашки я именно так решал.

Информационные источники:
Искусственный интеллект. Современный подход (книга)
Artificial Intelligence (онлайн курс от института Беркли)

Т.е мне по сути нужно будет дерево

10
   /   |   \     \
 10  1   8    7
                 / |   \  \
                1 7  10   8

и так далее в зависимости от количества возможных элементов?
или как, а то вообще идей нет уже

Короче сдал и я вот не пойму, не проходило тест из за того что ифка для проверки выхода за границе находилась в начале функции, а не перед ее вызовом, как то так.
Все было гениально просто

nerv_, за инфу спасибо, летом по читаю))

рони, тебе тоже спасибо за варианты