I can find many examples of the Knapsack Problem being done in Java, but none se

Question

I can find many examples of the Knapsack Problem being done in Java, but none seem to do it quite the way my assignment is requesting. I appreciate any help that can be offered. Again this is for Java, and recursion is to be used to solve the problem.

Implementing a Solution

Implementing a solution to the Knapsack problem is not difficult: it just will take a very long time to run if there are many weights. Here we will describe a recursive approach that you will render into code. The basic method is the helper method maximize, described here:

/*Return the maximum value, but no greater than limit, that can be obtained by adding up elements from weights using those elements from index 0 up to, but not including, index upTo. @param weights Positive numbers listed in increasing order. @param limit Greater than or equal to 0 @param upTo Less than or equal to the length of the array weights and greater than or equal to 0 @return The maximum value that can be obtained.*/

public static int maximize(int[] weights, int limit, int upTo) {

The idea is that maximize will solve the knapsack problem for the set of weights weights[0], … , weights[upTo-1] and the limit parameter.

Here a description of the method:

If either limit is 0 or upTo is 0, just return 0. In these cases there are either no weights or nothing can be stored.

If the limit is greater than or equal to weight[upTo-1]. try using weight[upTo-1] and seeing how much can be packed in using that weight along with others

maximize will call itself passing the weights array, a second parameter computed as the original limit minus weight[upTo-1] , and with the third parameter upTo-1.

The best that can be done will be the result returned by the recursive call plus weight[upTo-1]

Now try solving the problem without using weight[upTo-1]

maximize will call itself with the same weight and the same limit. The third parameter will be upTo-1.

The result to return from the method will be the larger of the two values computed in the previous two steps.

If weight[upTo-1] is less than limit, so the step above was not attempted, just return the value from the previous step.

For convenience, we would use the following method to start off the computation;

public static int maximize(int[] weights, int limit)

This method simply calls the maximize described above with the same weights and limit but with the third parameter the length of the weights array.

Here are some examples to test with. Of course you can use the five weight example used above as well. The weights have been listed here in a way to use them in an array initializer.

Bonus Challenge

The method you will write above is fine but it does not tell you which weights were finally chosen. This challenge problem asks you to correct that by implementing these two methods:

public static Set maximizeSol(int[] weights, int limit, int upTo) {

public static Set maximizeSol(int[] weights, int limit) {

Weights Limit Max Pack 19, 30, 130, 137, 173, 182, 209, 225, 259, 260 1082 1082 19, 30, 130, 137, 173, 182, 209, 225, 259, 260 1574 1494 9, 54, 138, 143, 157, 160, 171, 172, 175, 196, 213, 223, 228, 246, 283 2504 2430

Explanation / Answer

import java.util.*;

public class Recursion_weight
{

    private Sack bagOfRecursion_weight = new Sack();
    private Sack knapSack = new Sack();

    public static void main(String[] args){
        Recursion_weight myRecursion_weight = new Recursion_weight();
        myRecursion_weight.bagOfRecursion_weight.add(2);
        myRecursion_weight.bagOfRecursion_weight.add(3);
        myRecursion_weight.bagOfRecursion_weight.add(4);
        myRecursion_weight.bagOfRecursion_weight.add(5);
        myRecursion_weight.bagOfRecursion_weight.add(6);
        myRecursion_weight.bagOfRecursion_weight.add(8);
      
        System.out.println("Possible answers: ");
        myRecursion_weight.fillKnapSack(13);
    }
  
    public void fillKnapSack(int targetWeight){
        knapSack.empty();
        fillKnapSackRec(targetWeight, 0);
    }
  
    public void fillKnapSackRec(int targetWeight, int i){

        if(i == bagOfRecursion_weight.size())
        {
            if(targetWeight == 0){
                System.out.print("result is:");
                for (int j = 0; j < knapSack.size(); j++){
                    System.out.print(knapSack.getWeight(j) + " ");
                }
                System.out.println("");
            }
            return;
        }
      
        knapSack.add(bagOfRecursion_weight.getWeight(i));
        fillKnapSackRec(targetWeight - bagOfRecursion_weight.getWeight(i), i+1);
        knapSack.remove(knapSack.size()-1);
        fillKnapSackRec(targetWeight, i+1);     
    }
  
  
    class Sack extends ArrayList
    {
      
        public Sack(){
            super();
        }
  
        public void add(int weight){
            add(new Integer(weight));
        }
  
  
        public int getWeight(){
            int sackWeight = 0;
            for (int i = 0; i < size(); i++){
                Integer nextWeight = (Integer)get(i);
                sackWeight = sackWeight + nextWeight.intValue();
            }
            return sackWeight;  
        }
  
        public int getWeight(int n){
            int w = -1;
            if (n < size()){
                Integer weight = (Integer)get(n);
                w = weight.intValue();
            }
            return w;
        }
              
        public boolean isEmpty(){
            return (size() == 0);
        }
      
        public void shuffle(){
            Collections.shuffle((List)this);
        }
      
        public void empty(){
            clear();
        }
      
    }
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.