1 #include <stdio.h>

 2 #define LEN 10

 3 #define NEGINF    -999999

 4 struct r_d {

 5     int r;    //profit

 6     int s;    //distance

 7 };

 8

 9 int price[LEN+1] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

10

11 int cut_rod(int price[], int n)

12 {

13     /*

14     DP-1-cut-rod.c:9:8: error: variable-sized object may not be initialized

15         int r[n+1] = {0, price[1]};

16               ^~~

17     int r[n+1] = {0, price[1]};

18     */

19     int r[LEN+1] = {0, price[1]};

20     int i, j, max;

21

22     for (i = 2; i <= n; i++) {

23         max = NEGINF;

24         for (j = i; j >= 1; j--)

25             max = (max > r[i-j] + price[j]) ? max : (r[i-j]+price[j]);

26         r[i] = max;

27     }

28     return r[n];

29 }

30

31 int extend_cut_rod(int price[], int n)

32 {

33     int r[LEN+1], s[LEN+1];

34     int i, j, max;

35     struct r_d sol;

36

37     r[0] = 0, s[0] = 0;

38     for (i = 1; i <= n; i++) {

39         max = NEGINF;

40         for (j = i; j >= 1; j--) {

41             if (max < r[i-j] + price[j]) {

42                 max = r[i-j] + price[j];

43                 s[i] = j;

44             }

45         }

46         r[i] = max;

47     }

48     for (i = 0; i <= n ; i++)

49         printf("extend_cut_rod.  s[%d] = %d\n", i, s[i]);

50     printf("===========================================\n");

51     for (i = 0; i <= n ; i++)

52         printf("extend_cut_rod.  r[%d] = %d\n", i, r[i]);

53     return r[n];

54 }

55

56 int extend_cut_rod_2(int price[], int n)

57 {

58     int r[LEN+1], s[LEN+1];

59     int i, j, max;

60     struct r_d sol;

61

62     r[0] = 0, s[0] = 0;

63     for (i = 1; i <= n; i++) {

64         max = NEGINF;

65         for (j = 1; j <= i; j++) {

66             if (max < r[i-j] + price[j]) {

67                 max = r[i-j] + price[j];

68                 s[i] = j;

69             }

70         }

71         r[i] = max;

72     }

73     for (i = 0; i <= n ; i++)

74         printf("extend_cut_rod_2.  s[%d] = %d\n", i, s[i]);

75     printf("===========================================\n");

76     for (i = 0; i <= n ; i++)

77         printf("extend_cut_rod_2.  r[%d] = %d\n", i, r[i]);

78     return r[n];

79 }

80

81 int main(int argc, char *argv[])

82 {

83     int r, i;

84

85     for (i = 0; i <= LEN; i++) {

86         r = cut_rod(price, i);

87         printf("cut-rod   r%d = %d\n", i, r);

88     }

89     printf("===========================================\n");

90     extend_cut_rod(price, 10);

91     printf("===========================================\n");

92     extend_cut_rod_2(price, 10);

93

94     return 0;

95 }