我有一个家庭作业挣扎，我相信我大大过于复杂的解决方案，需要从任何人愿意提供它的一些帮助。 让我来解释分配一些基本规则。
下面是一个有确切的问题informatation另一篇文章的链接。
如何解决递归的“经典”背包算法？
一组数字将给予诸如例如：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;
}
}
