递归背包Java [英] Recursive Knapsack Java
问题描述
我正忙于完成一项家庭作业，我认为该解决方案过于复杂，需要任何愿意提供该解决方案的人提供一些帮助.让我解释一下分配的一些基本规则.
I'm struggling with a homework assignment and I believe I am vastly over-complicating the solution and need some help from anyone willing to offer it. Let me explain some ground rules for the assignment.
下面是指向具有确切问题信息的另一篇文章的链接.
Below is a link to another post that has the exact problem informatation.
将给出一组数字，例如:15、11、8、7、6、5.第一个数字始终对应于背包的目标或容量.我必须做的是递归地检查所有数字，看看是否有任何数字加起来有背包容量.如果是这样，我将打印出总计为目标总和的数字，然后然后继续检查其他可能的解决方案.在研究此问题时，大多数职位都会解决一种解决方案.让我解释一下分配的基本规则.
A set of numbers will be given such as for example: 15, 11, 8, 7, 6, 5. The first number always corresponds to the target or capacity of the knapsack. What I must do is recursively check all the numbers and see if any of the numbers add up to the capacity of the knapsack. If they do, I am to print the numbers that add up to the target sum and then continue checking for other possible solutions. When researching this problem, most posts solve for one solution. Let me explain the ground rules for the assignment.
此分配必须递归完成，没有例外. 必须找到所有解决方案 数字从高到低排序.
This assignment must be done recursively, no exceptions. All solutions must be found The numbers are sorted from highest to lowest.
在15、11、8、7、6、5中，只有8 + 7 + 5 = 15的一种解决方案.但是，给定一个数据集，例如15、10、9、8、7、6， 5，4，3，2存在多个解决方案，例如.
In the 15, 11, 8, 7, 6, 5 There was only one solution of 8 + 7 + 5 = 15. However, given a data set such as 15, 10, 9, 8, 7, 6, 5, 4, 3, 2 there exist multiple solutions such as.
10 + 5 = 15
9 + 6 = 15
8 + 7 = 15
基本上，有两个问题需要解决.
Essentially there are two problems to solve.
考虑到您陈述的问题(指定必须使用递归)，这个想法很简单:对于您可以接受的每个项目，看看是否更好.所以只有两种可能的途径 你拿这个东西 你不接受 拿走物品时，将其从列表中删除，并通过物品的重量减少容量. 如果您不拿走物品，则从列表中删除if，但不会减少容量.
The idea, given the problem you stated (which specifies we must use recursion) is simple: for each item that you can take, see if it's better to take it or not. So there are only two possible path you take the item you don't take it When you take the item, you remove it from your list and you decrease the capacity by the weight of the item. When you don't take the item, you remove if from you list but you do not decrease the capacity.
在解决此解决方案中作者所说的问题时，我遇到了一些麻烦.
I'm having some trouble getting my mind around what the author in this solution was saying.
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
我不明白的是，如果我不加数字怎么办?
What I'm failing to understand is what do I do if I don't add a number?
您拿走一个物品:从列表中删除该物品并减少容量 您不带物品:您从列表中删除了该物品，但不会减少容量.
You take an item: You remove the item from your list and decrease the capacity You dont take an item: You remove the item from your list but you don't decrease the capacity.
在我的代码中，无论是摄取物品"还是不摄取物品"，我都不会从体重清单中删除物品，我认为这是我的问题.
In my code, in either case of "take item" or "dont take item", I do not remove an item from my weight list and I think this is my problem to begin with.
我将在下面为此作业发布一些我正在处理的代码.如您所见，有一个过于肿的解决方案，其效果不如真正的解决方案那么优雅.如果有人可以通过上述分配参数提供有关如何真正解决此问题的建议或见识，我将不胜感激.谢谢.
I'll post some code I've worked on below for this assignment. As you can see, there is is an overly bloated solution that does not work as elegantly as the real solution should. If anyone could provide advice or insight on how to really solve this problem with the assignment parameters mentioned above, I would greatly appreciate it. Thank you.
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;
}
}
推荐答案
您描述的问题实际上是特例，其中您只有项目权重，而没有利润-或者权重和利润相等.这个问题通常不称为背包，而是子集总和的最大化版本.
The problem you described is actually a special case where you have only items weights, but no profits - or alternatively the weights and the profits are equal. This problem isusually not termed as Knapsack but the maximization version of Subset Sum.
此外，对于递归解决方案，除了输入外，不需要任何数组.
Furthermore, for a recursive solution no array besides the input is needed.
假设商品大小在长度为n的weightweight数组(此处从零开始，以磅为单位)中给出，容量表示总容量.
Suppose the item sizes are given in the array weightArray (indices zero-based here) of length n and capacity denoted the total capacity availabel.
定义(首先在概念上，而不是在代码中)函数
Define (first conceptually, not in code) the function
F( remainingCapacity, i ) :=
maximum total weight attainable for items
with indices in {0,..,i} of infinity if no such solution exists
请注意
F(容量，n-1)
给出了解决问题的方法.此外，F具有属性
yields the solution to the problem. Additionally, F has the property
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 ) )
其中，最大值表达式中的第一项对应于采取项i"的情况，而第二表达式对应于不采取项i"的情况.上面的情况或多或少可以很容易地转化为实际的实现.
where the first term in the maximum expression corresponds to the "take item i" case and the second expression corresponds to the "don't take item i" case. The cases above can more or less easily transformed to an actual implementation.
但是请注意，这只会产生选择项所能达到的最大值，而不是实际选择项本身.
However note that this will yield only the maximum value attainable by a choice of items, but not the actual choice of items itself.
这篇关于递归背包Java的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
