Recursive Knapsack Java

Question

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.

How do I solve the 'classic' knapsack algorithm recursively?

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.

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.

From the previous post linked up above:

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;
    }
}

Answer 1

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.

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

note that

F( capacity, n - 1 )

yields the solution to the problem. Additionally, F has the property

F( remainingCapacity, -1 ) = 0 if remainingCapacity >= 0 

and

F( remainingCapacity, i ) =
Infinity (can be simulated by a sufficiently
large integer) if remainingCapacity < 0

and

F( remainingCapacity, i ) =
max( F( remainingCapacity - weightArray[ i ], i - 1 ),
     F( remainingCapacity, i - 1 ) )

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.