I am trying to devise a program to scheduling "events" onto 3 different stages using dynamic programming. I have a start time a finish time and an interval associated with each event.

``````int max1(int x,int y)
{
if (x>y)
{
return x;
}
return y;
}

int max2(int x, int y, int z)
{
int temp = max1(x,y);
if (z > temp)
{
return z;
}
return temp;
}

int n,start[SIZE],finish[SIZE],value[SIZE],preceding[SIZE],M[SIZE][SIZE][SIZE],
room1[SIZE],room2[SIZE], room3[SIZE];
//

// Input: int array a[] with n elements in ascending order.
//        int key to find.
// Output: Returns subscript of the last a element <= key.
//         Returns -1 if key<a[0].
// Processing: Binary search.

int binSearchLast(int *i,int n,int key)
{
int low,high,mid;
low=0;
high=n-1;

{
mid=(low+high)/2;
if (i[mid]<=key)
low=mid+1;
else
high=mid-1;
// subscripts between low and high are in search range.
// size of range halves in each iteration.
// When low>high, low==high+1 and a[high]<=key and a[low]>key.
}
return high;
}

void main()
{
int i,j,k,sum=0,r1Count=0,r2Count=0, r3Count = 0;

scanf("%d",&n);
finish[0]=(-999999);
for (i=1;i<=n;i++)
{
scanf("%d %d %d",&start[i],&finish[i],&value[i]);
}

for (i=1;i<=n;i++)
{
preceding[i]=binSearchLast(finish,n+1,start[i]);
}

for (i=0;i<=n;i++){
for (j=0;j<=n;j++){
for(k=0;k<=n;k++){

if (i == 0 && j == 0 && k == 0)
{

M[i][j][k] = 0;
}

else if (i>j && i>k)
{

M[i][j][k] = max1(M[preceding[i]][j][k]+value[i],
M[i-1][j][k]);
}
else if (j>i && j>k)
{

M[i][j][k] = max1(M[i][preceding[j]][k]+value[j],
M[i][j-1][k]);
}
else if (k>i && k>j)
{

M[i][j][k] = max1(M[i][j][preceding[k]]+value[k],
M[i][j][k-1]);
}

else if (i == 0)
{

M[i][j][k] = max1(M[i][j-1][k],M[i][j][k-1]);
}
else if (j == 0)
{

M[i][j][k] = max1(M[i-1][j][k], M[i][j][k-1]);
}
else if (k == 0)
{

M[i][j][k] = max1(M[i-1][j][k], M[i][j-1][k]);
}
else
{

M[i][j][k] = max2(M[i-1][j][k], M[i][j-1][k], M[i][j][k-1]);
}

}

}
//printf("M[%d][%d][%d] = %d\n", i, j, k, M[i][j][k]);
}
``````

//
//
printf("M[16][16][16] is %d", M[16][16][16]);

for the input

16
10 20 1
15 25 2
10 30 3
20 40 1
15 45 2
30 50 1
40 60 2
25 65 3
50 70 1
35 75 3
60 80 2
15 85 4
70 90 1
35 95 3
80 100 2
72 110 3

It is suppose to return a max value of 22 for M[n][n][n] but mine is returning 13. Can anyone shed some light on what is wrong in my cost function?

I don't mean to alarm you, but your program doesn't have a cost function. ;)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.