Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 15.05.2016, 01:16
Аватар для cyber
I am Student
Отправить личное сообщение для cyber Посмотреть профиль Найти все сообщения от cyber
 
Регистрация: 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);

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

какие то мелкие оптимизации не имею смысла код переписан с С++, я не могу оригинальный код вкинуть потому что система поиска плагиата меня отмыеет потом)) (это для универа).
__________________
Цитата:
Если ограничения и условия описываются как "коробка", то хитрость в том что бы найти именно коробку... Не думайте о чем то глобальном - найдите коробку.
Ответить с цитированием
  #2 (permalink)  
Старый 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>
Ответить с цитированием
  #3 (permalink)  
Старый 15.05.2016, 02:44
Аватар для cyber
I am Student
Отправить личное сообщение для cyber Посмотреть профиль Найти все сообщения от cyber
 
Регистрация: 17.12.2011
Сообщений: 4,415

рони, хм, а это идея, записать все возможные комбинации, а потом отфильровать, попробую, но мне кажется лимит по памяти не пройдет)
Спасибо за вариант, сейчас перепишу на С++))
__________________
Цитата:
Если ограничения и условия описываются как "коробка", то хитрость в том что бы найти именно коробку... Не думайте о чем то глобальном - найдите коробку.
Ответить с цитированием
  #4 (permalink)  
Старый 15.05.2016, 12:59
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 33,120

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

Последний раз редактировалось рони, 15.05.2016 в 13:02.
Ответить с цитированием
  #5 (permalink)  
Старый 15.05.2016, 13:38
Аватар для cyber
I am Student
Отправить личное сообщение для cyber Посмотреть профиль Найти все сообщения от cyber
 
Регистрация: 17.12.2011
Сообщений: 4,415

рони, не прошло, в 2 раза превысило лимит памяти
Изображения:
Тип файла: png Screenshot from 2016-05-15 12-37-43.png (9.9 Кб, 7 просмотров)
__________________
Цитата:
Если ограничения и условия описываются как "коробка", то хитрость в том что бы найти именно коробку... Не думайте о чем то глобальном - найдите коробку.
Ответить с цитированием
  #6 (permalink)  
Старый 15.05.2016, 14:48
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 33,120

cyber,
тогда строить дерево ветка больше лимита отрезаем , ветка равна лимиту отрезаем в результат, меньше лимита оставляем и наращиваем.
Ответить с цитированием
  #7 (permalink)  
Старый 15.05.2016, 14:52
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 33,120

cyber,
количество всех вариантов известно заранее 6 * 4 * 4 * 8 ... и не хранить все варианты а только верные результаты и четыре индекса.
Ответить с цитированием
  #8 (permalink)  
Старый 15.05.2016, 15:09
Аватар для cyber
I am Student
Отправить личное сообщение для cyber Посмотреть профиль Найти все сообщения от cyber
 
Регистрация: 17.12.2011
Сообщений: 4,415

рони, по сути больше проблема с временем работы чем с памятью, по сути при рекурсии я и так отбрасываю лишние и дальше не иду. Но еще по страдаю если не заработает то сделаю деревом, может так получится
__________________
Цитата:
Если ограничения и условия описываются как "коробка", то хитрость в том что бы найти именно коробку... Не думайте о чем то глобальном - найдите коробку.
Ответить с цитированием
  #9 (permalink)  
Старый 15.05.2016, 15:17
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 33,120

cyber,
рекурсия кушает память как известно. может проще генерировать последовательно по одному и проверять подошёл не подошёл (это без оптимизации) ... 4 вложенных for c continue -- самый оптимальный вариант(для данного случая) ... понятно что нужен универсальный вариант.
Ответить с цитированием
  #10 (permalink)  
Старый 15.05.2016, 15:41
Аватар для cyber
I am Student
Отправить личное сообщение для cyber Посмотреть профиль Найти все сообщения от cyber
 
Регистрация: 17.12.2011
Сообщений: 4,415

Сообщение от рони
рекурсия кушает память как известно
да, я знаю, та версия алгоритма что у меня есть не проходит по времени по памяти норм, попробую еще раз на форах, если нет то перехожу к деревьям, хотя я реально не пойму как у некоторых одногрупников это заработало через рекурсию...
__________________
Цитата:
Если ограничения и условия описываются как "коробка", то хитрость в том что бы найти именно коробку... Не думайте о чем то глобальном - найдите коробку.
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Расписать алгоритм траскрибирования за $$$ wekze Общие вопросы Javascript 0 24.06.2014 20:55
Необычный алгоритм. Неповторяющиеся числа. broadcast77 Общие вопросы Javascript 5 13.01.2014 10:46
Как написать алгоритм выборки в javascript? Isaac Общие вопросы Javascript 13 06.02.2013 11:15
Волновой алгоритм Ли с 8-ми направлениями boy_cow Общие вопросы Javascript 6 04.10.2012 21:08
Спецификация Ecma-262. Пункт 8.7.2 PutValue(V,W) не до конца ясен алгоритм. vandy3 Общие вопросы Javascript 0 09.01.2012 17:31