Рекурсивный рюкзак Java
Я борюсь с домашним заданием и считаю, что сильно усложняю решение и нуждаюсь в помощи от любого, кто захочет его предложить. Позвольте мне объяснить некоторые основные правила для этого задания.
Ниже приведена ссылка на другой пост, в котором есть точная информация о проблеме.
Как мне рекурсивно решить "классический" алгоритм ранца?
Будет задан набор чисел, например: 15, 11, 8, 7, 6, 5. Первое число всегда соответствует цели или вместимости ранца. То, что я должен сделать, это рекурсивно проверить все числа и посмотреть, если какие-либо из этих цифр складываются в емкость ранца. Если они это сделают, я должен напечатать числа, которые в сумме составляют целевую сумму, а затем продолжить проверку других возможных решений. При исследовании этой проблемы большинство сообщений решают одно решение. Позвольте мне объяснить основные правила для назначения.
Это назначение должно быть сделано рекурсивно, без исключений. Все решения должны быть найдены. Числа отсортированы по возрастанию.
В 15, 11, 8, 7, 6, 5 было только одно решение 8 + 7 + 5 = 15. Однако, учитывая набор данных, такой как 15, 10, 9, 8, 7, 6, 5, 4, 3, 2 существует несколько решений, таких как.
10 + 5 = 15
9 + 6 = 15
8 + 7 = 15
По сути, есть две проблемы, которые необходимо решить.
Из предыдущего поста, связанного выше:
Идея, учитывая поставленную вами проблему (которая указывает на то, что мы должны использовать рекурсию), проста: для каждого предмета, который вы можете взять, посмотрите, лучше его взять или нет. Таким образом, есть только два возможных пути, по которым вы берете предмет, который вы не берете. Когда вы берете предмет, вы удаляете его из списка и уменьшаете емкость на вес предмета. Если вы не берете предмет, вы удаляете его из списка, но не уменьшаете емкость.
У меня возникли некоторые проблемы, связанные с тем, что говорил автор этого решения.
For example: Assuming a number set of 20, 11, 8, 7, 6,5
1. Target is 20
2. Read in number from set: 11
4. 11 < 20, Add 11 to solution
5. New target is 9 (20 - 11)
6. Read in the next number: 8
7. 8 is less than 9, Add 8 to solution
8. New target is 1 (20 - 19)
9 Read in 7, 7 is larger than 1, do not add 7
Что я не понимаю, что мне делать, если я не добавлю номер?
Вы берете предмет: Вы удаляете предмет из своего списка и уменьшаете емкость. Вы не берете предмет: Вы удаляете предмет из своего списка, но не уменьшаете емкость.
В моем коде, в любом случае "взять предмет" или "не брать предмет", я не удаляю элемент из своего списка весов, и я думаю, что это моя проблема с самого начала.
Ниже я выложу код, над которым работал, для этого задания. Как видите, существует слишком раздутое решение, которое работает не так элегантно, как реальное решение. Если бы кто-нибудь мог дать совет или понять, как действительно решить эту проблему с помощью параметров назначения, упомянутых выше, я был бы очень признателен. Спасибо.
import java.io.PrintWriter;
import java.util.ArrayList;
import javax.swing.JOptionPane;
public class Knapsack
{
public static void main(String[] args)
{
//Read in user input first
int[] tempArray;
String userInput = JOptionPane.showInputDialog("Enter a list of numbers delimited by a single space.");
String[] splitElements = userInput.split("\\s+");
//User array will contain the exact amount of
//numbers as long as extra spaces are not entered.
tempArray = new int[splitElements.length];
for(int i = 0; i < tempArray.length; i++)
{
tempArray[i] = Integer.parseInt(splitElements[i]);
}
Recursion recObj = new Recursion(tempArray);
}
}
class Recursion
{
private int[] weightArray;
private int [] solutionArray;
private int counter;
private int mainGoal;
private int [] backupOfOriginal;
private int solutionArrayCounter;
private ArrayList numberList;
private ArrayList previousSolutionsFound;
private int passThrough;
private int baseIterator;
private ArrayList distinctSolutions;
public Recursion(int[] paramArray)
{
weightArray = paramArray;
backupOfOriginal = weightArray;
solutionArray = new int[paramArray.length];
//Start at index 1 where the first number technically starts.
counter = 0;
//Keep track of main goal
mainGoal = weightArray[0];
solutionArrayCounter = 0;
passThrough = 0;
baseIterator = 0;
distinctSolutions = new ArrayList();
numberList = new ArrayList();
previousSolutionsFound = new ArrayList();
for(int i = 1; i < weightArray.length; i++)
{
numberList.add(weightArray[i]);
}
//Begin the recursive problem.
CheckForSums(mainGoal, numberList);
}
public void CheckForSums(int targetValue, ArrayList weightArray)
{
int numberRead = (Integer) weightArray.get(counter);
targetValue = ComputeTarget();
counter++;
//Base case if any number to read
//is greater than the main target value
//remove it
if(numberRead > mainGoal)
{
weightArray.remove(counter);
counter--;
}
if(numberRead <= targetValue)
{
AddToSolution(numberRead);
CheckForPossibleSolution();
//Add the item to the solution
}
//counter++;
if(counter == weightArray.size())
{
passThrough++;
counter = passThrough + 1;
RemoveOneFromSolution();
}
//Advance forward one position
if(passThrough == weightArray.size() - 1)
{
counter = 0;
passThrough = 0;
weightArray = RebuildArrayList(weightArray);
for(int i = 0; i < baseIterator; i++)
{
weightArray.remove(0);
}
baseIterator++;
ResetSolutionArray();
}
if(baseIterator == this.weightArray.length - 2)
{
//Should be completely done
return;
}
CheckForSums(targetValue, weightArray);
}
public void ResetSolutionArray()
{
solutionArrayCounter = 0;
for(int i = 0; i < solutionArray.length; i++)
{
solutionArray[i] = 0;
}
}
public void CheckForPossibleSolution()
{
if(SumOfSolutionsFound() == mainGoal)
{
PrintFoundSolution();
RemoveDownToBaseNumber();
}
else
{
System.out.println("No solution found yet.");
}
}
public void RemoveOneFromSolution()
{
if(solutionArrayCounter > 1)
{
solutionArrayCounter--;
}
if(solutionArrayCounter > 1)
{
solutionArray[solutionArrayCounter] = 0;
}
}
public void RemoveDownToBaseNumber()
{
while(solutionArrayCounter > 1)
{
solutionArrayCounter--;
solutionArray[solutionArrayCounter] =0;
}
}
public int SumOfSolutionsFound()
{
int sumOfSolutions = 0;
for(int i = 0; i < solutionArray.length; i++)
{
sumOfSolutions += solutionArray[i];
}
return sumOfSolutions;
}
public ArrayList<Integer> RebuildArrayList(ArrayList<Integer> paramList)
{
paramList = new ArrayList();
for(int i = 1; i < weightArray.length; i++)
{
paramList.add(weightArray[i]);
}
return paramList;
}
public void PrintFoundSolution()
{
StringBuilder toMessageBox = new StringBuilder();
System.out.print("Found a solution! ");
toMessageBox.append("Found a Solution! ");
for(int i = 0; i < solutionArray.length; i++)
{
System.out.print(solutionArray[i] + " ");
toMessageBox.append(solutionArray[i] + " ");
}
String finishedMessage = toMessageBox.toString();
boolean displayCurrentSolution = true;
for(int i = 0; i < previousSolutionsFound.size(); i++)
{
String previousSolution = previousSolutionsFound.get(i).toString();
if(finishedMessage.equals(previousSolution))
{
displayCurrentSolution = false;
}
}
previousSolutionsFound.add(finishedMessage);
if(displayCurrentSolution == true)
{
distinctSolutions.add(finishedMessage);
JOptionPane.showMessageDialog(null, finishedMessage,
"Solution for target: " + mainGoal, JOptionPane.INFORMATION_MESSAGE);
}
}
public void AddToSolution(int value)
{
solutionArray[solutionArrayCounter] = value;
solutionArrayCounter++;
}
public int ComputeTarget()
{
int sumOfSolutions = 0;
for(int i = 0; i < solutionArray.length; i++)
{
sumOfSolutions += solutionArray[i];
}
int numbersNeededToReachMainGoal = mainGoal - sumOfSolutions;
return numbersNeededToReachMainGoal;
}
}
1 ответ
Проблема, которую вы описали, на самом деле является особым случаем, когда у вас есть только веса предметов, но нет прибыли - или, наоборот, веса и прибыль равны. Эта проблема обычно называется не рюкзаком, а версией максимизации суммы подмножеств.
Кроме того, для рекурсивного решения не нужен массив, кроме входных данных.
Предположим, что размеры элемента даны в массиве weightArray (здесь индексы начинаются с нуля) длины n, а емкость обозначает общую доступную емкость.
Определить (сначала концептуально, а не в коде) функцию
F( remainingCapacity, i ) :=
maximum total weight attainable for items
with indices in {0,..,i} of infinity if no such solution exists
Обратите внимание, что
F(емкость, н - 1)
дает решение проблемы. Кроме того, F имеет свойство
F( remainingCapacity, -1 ) = 0 if remainingCapacity >= 0
а также
F( remainingCapacity, i ) =
Infinity (can be simulated by a sufficiently
large integer) if remainingCapacity < 0
а также
F( remainingCapacity, i ) =
max( F( remainingCapacity - weightArray[ i ], i - 1 ),
F( remainingCapacity, i - 1 ) )
где первое слагаемое в максимальном выражении соответствует случаю "take item i", а второе выражение соответствует случаю "take take i". Вышеприведенные случаи могут быть более или менее легко преобразованы в фактическую реализацию.
Однако обратите внимание, что это даст только максимальное значение, достижимое при выборе предметов, но не фактический выбор самих предметов.