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?