CODEWITHSUNDEEP
javaalgorithmdynamic-programmingknapsack-problem
kotseman
kotseman

Reputation: 57

How to know which item was selected in the knapsack problem(DP implementation)?

I am implementing the knapsack problem based on this code and I want to know which items were finally selected.

the code:

Knapsack { 


static int max(int a, int b)  { return (a > b) ? a : b; } 


static int knapSack(int W, int wt[], int val[], int n) 
{ 
    int i, w; 
    int K[][] = new int[n + 1][W + 1]; 

    // Build table K[][] in bottom up manner 
    for (i = 0; i<= n; i++) { 
        for (w = 0; w<= W; w++) { 
            if (i == 0 || w == 0) 
                K[i][w] = 0; 
            else if (wt[i - 1]<= w) 
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]); 
            else
                K[i][w] = K[i - 1][w]; 
        } 
    } 

    return K[n][W]; 
} 


public static void main(String args[]) 
{ 
    int val[] = new int[] { 60, 100, 120 }; 
    int wt[] = new int[] { 10, 20, 30 }; 
    int W = 50; 
    int n = val.length; 
    System.out.println(knapSack(W, wt, val, n)); 

     } 

  }

What I want to do though is to find which items were finally inserted in to the knapsack based on how they were originally stored in the array and store those results on a file in binary format.

What I mean is, here we have 3 items in this piece of code and if for example item number 1 (the one that has a value of 60) and item number 3(the one that has a value of 120) were finally selected ,I would like to get a string that would look like that 1,0,1

Upvotes: 1

Views: 1629

Answers (1)

Chethan Bhateja
Chethan Bhateja

Reputation: 101

You can add the following to your code just before the return statement:

        int ind = n;
        int weight = W;
        String s = "";
        while (ind > 0) {
            if (K[ind][weight] != K[ind - 1][weight]) {
                s = "1," + s;
                weight -= wt[ind - 1];
            }
            else {
                s = "0," + s;
            }
            ind -= 1;
        }
        s = s.substring(0, s.length() - 1);
        System.out.println(s);

This code essentially backtracks from the final solution to see whether the maximum with i items is equivalent to the maximum with i - 1 items (which indicates whether the ith item was used).

After adding this to your code, I get the following output, which appears to be correct:

0,1,1
220

Upvotes: 1

Related Questions