Hey everyone,
I am working on writing a program that solves the knapsack problem. I have an array of weights in a class I called "Sack". I am trying to make a recursive method which tries to insert weights into a new array until the target weight has been met. The problem I have having is how I am going to keep track of things. A hint was given to me that for the recursive knapsack funtion, the target weight and the array index of where the remaining items start are the arguments. How can I keep track of what is being tested aritrarily? Any help would be greatly appreciated, and this is what I have so far for my Stack class
public class Sack
{
private int[] aSack, weights;
private int weightTarget;
private int weightIndex;
public Sack(int n, int j)
{
aSack = new int[n]; //creates a sack with capacity n.
weights = new int[j];
weightIndex = 0;
}
public void addWeights(int x)
{
if(weightIndex != weights.length)
{
weights[weightIndex] = x;
weightIndex++;
}
}
public void setTargetWeight(int n)
{
weightTarget = n; //sets sack target weight
}
public void knapSack(int index, int target)
{
}
}