I have a problem like this (knapsack type of problem): I have an array of these values.
Code:
table [16] = { 0, 1, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 53 }
Given an index, I have to divide that into smaller pieces, such that the sum of their contents is the largest possible.
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
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;
}
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?