Knapsack recursive solution with the part sets

Question

I have the recursive solution for knapsack problem in java, here's my code:

public class OptimalIncome{
final static int length[] = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
final static int price[] = new int[] {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
public static int totalLength = 9;

public static int bestCut(int i, int totalLength){
    if(i < 0){
        return 0;
    }
    else if(length[i] > totalLength){
        return bestCut(i - 1, totalLength);
    }
    else{
        return Math.max(bestCut(i - 1, totalLength), bestCut(i - 1, totalLength - length[i]) + price[i]);
    }
}

public static void main(String[] args){
    System.out.println("Given total rod length : " + totalLength);
    System.out.println("Maximum income         : " + bestCut(price.length-1, totalLength));
    System.out.println("Smaller part sets      : ");
}
}

It works just fine, as you can see I want to print the set of choices (smaller parts). How can I do that? Thanks

`as you can see I want to print the set of choices (smaller parts)` no idea what you mean in this sentence. What is the "set of choices"? — amit, May 06 '15 at 10:26
you want to print the actual picked objects not only the bestCut ? — yahya el fakir, May 06 '15 at 10:27
Yes, sorry I didn't explain the problem well enough. I want to see which items the program selects for the best cut — RedHood148, May 06 '15 at 10:29
Related/dupe, finding elements in the knspack optimal solution: [How to find which elements are in the bag, using Knapsack Algorithm?](http://stackoverflow.com/q/7489398/572670), [find items in knapsack bag](http://stackoverflow.com/q/29733993/572670). Don't want to mark dupe myself because I am the answerer of these, but these threads do handle with this issue. (One explains how to do it in DP solution, the other in recursive solution, which is your case). — amit, May 06 '15 at 10:30
@amit thanks I took a look at them, but they use matrices, mine is just an array, how can I implement it for my code? (sorry, I'm not that good at reusing other codes) — RedHood148, May 06 '15 at 10:35
@RedHood The second thread explains how to do it for your recursive code, though it might not be an exact dupe because these thread asks "what's wrong with my solution" more than "how to do it". Glad I didn't close it. — amit, May 06 '15 at 10:36

yahya el fakir · Accepted Answer · 2015-05-06T10:44:23.917

Here we go :

import java.util.ArrayList; import java.util.List;

public class OptimalIncome {
    final static int length[] = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    final static int price[] = new int[] { 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };
    public static int totalLength = 9;
    static List<Integer> pickedObjects = new ArrayList<Integer>();
    public static int bestCut(int i, int totalLength) {
        if (i < 0) {
            return 0;
        } else if (length[i] > totalLength) {
            return bestCut(i - 1, totalLength);
        } else {
            return Math.max(bestCut(i - 1, totalLength),
                    bestCut(i - 1, totalLength - length[i]) + price[i]);
        }
    }

    public static void printSolution(int i,int totalLength){
        if(i < 0)
            return;
        else if(length[i]>totalLength){
            printSolution(i-1, totalLength);
        }else{
            int sol1 = bestCut(i-1,totalLength);
            int sol2 = bestCut(i - 1, totalLength - length[i]) + price[i];
            // check whether the optimal solution coming from picking the object or not .
            if(sol1>sol2){
                printSolution(i-1, totalLength);
            }else{

                pickedObjects.add(i);
                printSolution(i-1, totalLength - length[i]);
            }
        }
    }
    public static void main(String[] args) {
        System.out.println("Given total rod length : " + totalLength);
        System.out.println("Maximum income         : "
                + bestCut(price.length - 1, totalLength));
        System.out.println("Smaller part sets      : ");
        printSolution(price.length-1, totalLength);
        for (Integer i : pickedObjects) {
            System.out.println("picked object: "+ i +" length : "+ length[i]+ " price "+ price[i]);
        }
    }
}

we just need to do an inverse recursion and check were did you get the optimal solution to construct the output.

Although i think you might add some memoisation to your solution so that it would be fast enough. Hope it helped.

Knapsack recursive solution with the part sets

1 Answers1