I have a problem like this (knapsack type of problem): I have an array of these values.

Given an index, I have to divide that into smaller pieces, such that the sum of their contents is the largest possible.Code:table [16] = { 0, 1, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 53 }

So say, an index of 3 corresponds to the value 0. But if I take the values of index 1 and 2 (3 total) it would then correspond to a value of 1+7 which is the largest possible.

This is what I have so far

However this algorithm falls for a the value of 16. It gives me the value of 15+1 (54), however the optimal solution is the value of 2*8 (56) ... Any ideas on the algorithm?Code:int knapSack ( int index, int * array, int arrayLen ) { int j, i; int min; int sum = 0; findMin(array, arrayLen, &min); for (i=arrayLen-1; i>=1; i-=1) { if (min*i <= array[i]) { for (j=index; j>=i; j-=i) { sum+=array[i]; if (j-i <= i) index = j-i; if (j==0 && i==0) continue; } } if (min == array[i]) { for (j=index; j>=i; j-=i) { sum+=array[i]; if (j-1 <= i) index = j-i; if (j==0 && i==0) continue; } } } return sum; }