c++ - Knapsack Backtracking Using only O(W) space -

so have code have written correctly finds optimal value knapsack problem.

int mat[2][size + 1]; memset(mat, 0, sizeof(mat));  int = 0; while(i < nitems) {     int j = 0;     if(i % 2 != 0)     {         while(++j <= size)         {             if(weights[i] <= j) mat[1][j] = max(values[i] + mat[0][j - weights[i]], mat[0][j]);             else mat[1][j] = mat[0][j];         }     }     else     {         while(++j <= size)         {             if(weights[i] <= j) mat[0][j] = max(values[i] + mat[1][j - weights[i]], mat[1][j]);             else mat[0][j] = mat[1][j];         }     }     i++; } int val = (nitems % 2 != 0)? mat[0][size] : mat[1][size]; cout << val << endl; return 0; 

this part udnerstand. trying keep same memory space, i.e. o(w), compute optimal solution using backtracking. finding trouble. hints have been given this

now suppose want optimal set of items. recall goal                                                           in finding optimal solution in part 1 find optimal path   entry k(0,0) entry k(w,n). optimal path must pass through   intermediate node (k,n/2) k; k corresponds remaining   capacity in knapsack of optimal solution after items n/2 + 1,...n   have been considered 

the question asked this.

implement modified version of algorithm part 2 returns not  optimal value, remaining capacity of optimal  solution after last half of items have been considered 

any apprecaited me started. thanks