Рекурсивного бен не будет масштабироваться

Question

я завершил задание которого функция требуется:

• Рекурсивного решение
• Емкость < = 100
• values.length < = 25
• только параметры мощность и индекс
• Допускается повторение значений

Я потратил несколько часов на изучение проблем с упаковкой и рюкзаком.

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

Предложения были бы весьма признательны. Да, это академическое задание, но я предпочел бы избавиться от проблем, чем просто дать и заработать B.

public void calculateCombinations(int capacity, int index) { 
    count++; 
    if(index < values.length) { 
     if(values[index] <= capacity) { 
      currentSolution.addLast(index); 
      if(values[index] == capacity) 
       flushSolution(); 
      else 
       capacity -= values[index]; 
     } 
     calculateCombinations(capacity, index + 1); 
    } else 
     if(currentSolution.peekLast() != null) 
      calculateCombinations(capacity + values[currentSolution.peekLast()], currentSolution.removeLast() + 1); 
} 

Answer 1

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

Другая техника - это то, что я называю «брекетинг». Скажем, вы ищете два числа, сумма которых равна 50, и у вас есть список, например {2, 3, 9, 18, 24, 29, 37, 45}. Вам не нужно проверять каждую комбинацию, потому что у вас не может быть двух значений более 25 или менее 25. Вам нужно только проверять номера с каждой стороны списка, то есть 45 + 2, 45 + 3, 45 + 9, STOP, следующее число, 37 + 2, 37 + 3 и т. д. Это брекетинг. Создавая набор правил и брекетинг вокруг среднего значения, вам нужно только проверить крошечную часть возможных комбинаций.

Bin упаковка - проблема поиска, потому что во многих случаях, поскольку вы не можете перечислить все возможные комбинации. Это как в шахматы; вы не можете рассчитать все возможные шаги, вы просто пытаетесь найти хороший.