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?

This article has been dead for over six months. Start a new discussion instead.