KnapSack - the array of puts last items index
<p>I created a array of max weights with N items (array K) but I have a problem with create a good array of index of put last item (array Q). It helps me a lot to solve my exercise.</p>

<p>Here is my code:</p>

<pre class="lang-java prettyprint-override"><code>    static int max(int a, int b) { return (a &gt; b)? a : b; } 

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

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

                K[i][w] = max(wt[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
                if(wt[i-1] + K[i-1][w-wt[i-1]] == max(wt[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w])){
                    Q[i][w] = i;
                }
                else{
                                  //HERE I dont know what i need to put in Q ;/
                   //Q[i][w] = i-1; 
                }
            }
            else{

                K[i][w] = K[i-1][w];
                                  //HERE I dont know what i need to put in Q ;/
                //Q[i][w] = i-1;
            }
            System.out.print(K[i][w] + " ");
        }
        System.out.println();
    }
    // table of last items index
        for(int ii = 0; ii &lt;= n; ii ++){
            for(int jj = 0; jj &lt;= W; jj++){
                System.out.print(Q[ii][jj] + " ");
            }
            System.out.println();
        }
    return K[n][W];
    }
    public static void main(String[] args) {
        int wt[] = new int[]{17, 11, 16, 21, 27, 15, 15, 20};  //This is weights of items
        int  W = 300;  //this is max capacity of backpack
        int n = wt.length;  //this is a number of items
        knapSack(W, wt, n);
        //System.out.println(knapSack(W, wt, n));
    }
</code></pre>

<p>The values of all items are the same.</p>