CODEWITHSUNDEEP
algorithmrecursiondynamic-programmingknapsack-problem
user3693167
user3693167

Reputation: 813

solving knapsack dynamic programming debugging

I tried to solve the classical knapsap problem myself. But I am getting a wrong answer as 108. Could you help me to figure out what I have done wrong. Here I am using recursion.

Weight limit is 10

answer is 5+3+2 ==> 25+15+14=54

public class KnapSack {
public static int[] weight={6,5,4,3,2};
public static int[] value={12,25,24,15,14};

public static void main(String[] args) {
    System.out.println(c(0,0,10));
}

public static int c(int currentElement,int currentValue,int currentReamainder){

    int p = 0;
    if(currentReamainder<=0) return currentValue;

    for(int i=currentElement;i<weight.length;i++){
        if(currentReamainder<weight[i]) return currentValue;
        p = Math.max(value[i]+c(i+1,currentValue+value[i],currentReamainder-weight[i]),c(i+1,currentValue,currentReamainder))
    }

    return p;
}

}

Update: What should I do to print the weights of the optimum solution ?

Upvotes: 0

Views: 119

Answers (1)

Pham Trung
Pham Trung

Reputation: 11284

Your error is this line

 p=Math.max(value[i]+c(i+1,currentValue+value[i],currentReamainder-weight[i]),c(i+1,currentValue,currentReamainder));

it should be

 int val = Math.max(value[i]+c(i+1,currentValue+value[i],currentReamainder-weight[i]),c(i+1,currentValue,currentReamainder));
 p = Math.max(val, p);

The last bug is when you both updating currentValue and return p at the same time, so imagine the last call, when the function return currentValue, plus the last value[i] in each step, so your result is double

So , your function should be (notice I have removed the currentValue parameter, which is not necessary):

public static int c(int currentElement,int currentReamainder){

    int p = 0;
    if(currentReamainder<=0) return 0;

    for(int i=currentElement;i<weight.length;i++){
        if(currentReamainder<weight[i]) break;//This line is not valid, only when the weight array is sorted(ascending order)
        int val = Math.max(value[i]+c(i+1,currentReamainder-weight[i]),c(i+1,currentReamainder));
        p = Math.max(val, p);
    }

    return p;
}

Upvotes: 1

Related Questions