Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Rod cutting algorithms from 15.1 of Intro to Algorithms (Dynamic Programming), implemented in 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.