我正在为家庭作业而苦苦挣扎，我相信我的解决方案过于复杂，需要任何愿意提供它的人的帮助。让我解释一下作业的一些基本规则。
下面是另一个帖子的链接，其中包含确切的问题信息。
将给出一组数字，例如：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
基本上有两个问题需要解决。
从上面链接的上一篇文章中：
考虑到您所说的问题（指定我们必须使用递归），这个想法很简单：对于您可以接受的每个项目，看看是否最好接受它。所以只有两种可能的路径你拿走你不拿的物品当你拿走物品时，你把它从你的清单中删除，你通过物品的重量减少容量。当您不拿该项目时，您将 if 从您的清单中删除，但您不会减少容量。
我很难理解作者在这个解决方案中所说的话。
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;
}
}