This is for a school assignment and the professor stipulates that recursion must be used, and it must take a single line input in a gui box where the first number is the max capacity (weight) the knapsack can hold and the rest are item weights. This doesn't include the value, just weight.
It is partially working, as it is following the tree properly and indicating how many solutions there are (via debugging output) but I am having trouble being able to record the valid solutions. It seems to work fine on returns from recursive calls when at the ends of the branches due to storing and removing the items from the sack[] array.
As far as I can tell from stepping through the code a million times is that it fails when returning somewhere else. This leaves stray items sitting in the sack that shouldn't be there. Hopefully someone will be able to see where I am doing something dumb and help me go in the correct direction. I have deleted and rewritten the code in this so many times that I am about to throw my computer out of a window. lol
I know this is a lot, but I couldn't think of how to properly describe what I am having trouble with other than just posting the entire program. Thanks in advance for any help anyone might be able to provide.
import javax.swing.*;
import java.util.Arrays;
// Main Program
class n00868494 {
static int itemCount = 0; // total number of items
static int pos = 0; // position indicator in the "sack" array
static int sack[] = new int[25]; // sack to hold items on right branches
public static void main(String[] args) {
String sinput[] = new String[25]; // temp string array to hold parameters before converting to integers
int items[] = new int[25]; // array to hold the items
int capacity = 0; // knapsack capacity
String s = null; // temp string to hold user input
while (true) { // infinite loop
// Use a JOptionPane dialog to get the user's input
s = JOptionPane.showInputDialog(new JFrame("Input Params"), "Please enter total weight, followed a list of item weights)","Run Parameters",JOptionPane.QUESTION_MESSAGE);
if ((s == null) || (s.equals(""))) { // user pressed X, cancel or left it blank.
System.exit(0); // exit cleanly
}
sinput = s.split(" "); // split the parameters on the whitespace
for (int i = 0; i < sinput.length; i++) { // iterate through the array and copy the elements to the correct variables
if (i == 0) {
capacity = Integer.parseInt(sinput[i], 10); // knapsack weight in the first position
} else {
items[i-1] = Integer.parseInt(sinput[i], 10); // the rest are item weights
}
}
items = Arrays.copyOfRange(items, 0, sinput.length - 1); // truncate the items array to remove empty elements at the end
knapSack(capacity, items); // call the knapsack method that will in turn call the recursive function
}
}
public static void knapSack(int capacity, int[] items) {
itemCount = items.length; // keep track of original number of items
recknapSack(capacity, items, 0); // start recursive calls
}
/*
recursive knapsack method: called repeatedly to find the correct combinations of items such that their weights
total to the max capacity that the knapsack can hold
capacity: knapsack capacity
items: array of items (weights)
branch: flag indicating whether the call is a left branch (item not included) or right branch (item included)
0 - initial call, non recursive
1 - left branch, weight not included
2 - right branch, weight included
*/
public static void recknapSack(int capacity, int[] items, int branch) {
System.out.print("\nCap: " + capacity + " Items: " + Arrays.toString(items)); // recursive call tracking debugging
if (capacity == 0){ // debugging - for breaking at certain points in the tree
assert Boolean.TRUE; // set breakpoint on this line
}
// base cases - ends of the branches
if (capacity == 0){ // sack is exactly full, item weights = total weight
System.out.print("\t -> good tree"); // debugging
//JOptionPane.showMessageDialog(new JFrame("Results"), "The valid combinations are: ");
Arrays.fill(sack, 0); // clear the sack, this was a successful branch, will start again for another solution
return;
} else if (capacity < 0) { // bag overloaded
System.out.print("\t -> overload tree"); // debugging
if (branch == 2) // if this is an "included" branch
sack[--pos] = 0; // remove the last item placed in the sack
return;
} else if (items.length == 0){ // out of items and/or capacity not reached
System.out.print("\t -> empty src tree"); // debugging
if (branch == 2)
sack[--pos] = 0;
return;
} else {
int firstItem; // this the first item, it will either be discarded (not included) or placed in the sack array (included)
firstItem = items[0];
items = Arrays.copyOfRange(items, 1, items.length); // for either recursive branch: remove the first item from the list
recknapSack(capacity, items, 1); // call recursive function, left branch, where item is discarded and not placed in sack
// prepare for right branch, where item is placed in sack
capacity -= firstItem; // subtract the left most item weight from from capacity
sack[pos++] = firstItem; // place the item in the sack
recknapSack(capacity, items, 2); // recursive right branch call, item is placed in sack, weight subtracted from capacity
}
return;
}
}
