Rod cutting algorithms from 15.1 of Intro to Algorithms (Dynamic Programming), implemented in C

rod_cutting.c

#include <stdio.h>
#include <stdlib.h>


// doesn't work for pointer (e.g. if array passed in as parameter)
#define ARRAYSIZE(arr) (int) (sizeof(arr) / sizeof(arr[0]))


// helper
int max_int(int x, int y) {
  int r;
  r = x ^ ((x ^ y) & -(x < y)); 
  return r;
}


int cut_rod_naive(int *p, int n) {
  if (n == 0) {
    return 0;
  }
  int q = -1;
  int i;
  for (i = 0; i < n; i++) {
    q = max_int(q, p[i] + cut_rod_naive(p, n - i - 1));
  }
  return q;
}


int memoized_cut_rod_aux(int p[], int n, int r[]) {
  if (r[n - 1] >= 0) {
    return r[n - 1];
  }
  int q;
  if (n == 0) {
    q = 0;
  } else {
    q = -1;
    int i;
    for (i = 0; i < n; i++) {
      // Pseudo code in book doesn't handle this case!
      int remainder = 0;
      if (n - (i + 1) > 0) {
        remainder = memoized_cut_rod_aux(p, n - (i + 1), r);
      }
      q = max_int(q, p[i] + remainder);
    }
  }
  r[n - 1] = q;
  return q;
}


int memoized_cut_rod(int p[], int n) {
  int r[n];
  int i;
  for (i = 0; i <= n; i++) {
    r[i] = -1;
  }
  return memoized_cut_rod_aux(p, n, r);
}


int bottom_up_cut_rod(int p[], int n) {
  int r[n+1];
  r[0] = 0;
  int i, j;
  for (i = 1; i <= n; i++) {
    int q = -1;
    for (j = 0; j < i; j++) {
      q = max_int(q, p[j] + r[i - j - 1]);
    }
    r[i] = q;
  }
  return r[n];
}


typedef struct results {
  int *r;
  int *s;
} result;


void bottom_up_cut_rod_ext(int p[], int n, result *res) {
  int r[n+1];
  int s[n+1];
  r[0] = 0;
  // To match indexing shown in book
  s[0] = 0;
  int i, j;
  for (i = 1; i <= n; i++) {
    int q = -1;
    for (j = 0; j < i; j++) {
      if (q < p[j] + r[i - j - 1]) {
        q = p[j] + r[i - j - 1];
        // To match indexing shown in book
        s[i] = j + 1;
      }
    }
    r[i] = q;
  }
  res->r = r;
  res->s = s;
}


void print_max_revenue(int max_revenue, int n) {
  fprintf(stdout, "Cut rod max revenue for length %d\n", n);
  printf("----------------\n");
  fprintf(stdout, "%d\n\n", max_revenue);
}


void print_result(result *res, int prices[], int n) {
  printf("Optimal cut by length\n");
  printf("----------------\n");
  printf("Length Cut Price\n");
  printf("----------------\n");
  int i;
  for (i = 0; i <= n; i++) {
    int p = 0;
    if (i - 1 >= 0) p = prices[i - 1];
    fprintf(stdout, "%d      %d   %d\n", i, res->s[i], p);
  }
}


int main(int argc, char *argv[]) {
  int prices[] = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
  int n = ARRAYSIZE(prices);
  int max_revenue = bottom_up_cut_rod(prices, n);
  print_max_revenue(max_revenue, n);

  result *res = malloc(sizeof(result));
  bottom_up_cut_rod_ext(prices, n, res);
  print_result(res, prices, n);
  free(res);

  return 0;
}