动态规划Dynamic Programming: Rod-Cutting Problem

动态规划可求最优解问题,但有条件限制,每一层最优解可知。

递归动态规划

与分治思想有类似之处,但在递归基础上,用一张表存储计算过程中每一层的”最优解“,避免重复计算已经得出的计算结果。

Rod-Cutting Problem

问题描述:

给你一根长n英尺的棒子和一份关于该棒子的价目表如下(其中 i = 1,2,3,…,n),请问如何将这根棒子卖出最高的价格,可以对棒子进行切割。

动态规划Dynamic Programming: Rod-Cutting Problem

 

 

thinking path:

从i=1 to 10进行枚举尝试,例如,砍1米开始砍,那么剩下的9米就会成为新的”问题“,进行递归。易得递推式:

r(i)=max(p[i]+r(n-i));  n为rod总长

根据递推式,写出递归伪代码:

CUT(p,n)

  if n==0 return 0;

  for (int i = 1; i <= n; i++) 

     q = max(q,p[i]+cut(p,n-i));

     return q;

 

 

结合Dynamic Programming思想:

用一个数组result来存放每一段的结果。

CUT(result,p,n)

  if (r[n]>=0) return r[n]

  if n==0 return 0

  else

      q=-∞

      for (int i = 1; i <= n; i++)

           if (q<p[i]+cut(result,p,n-i))

                   q=max(p[i]+cut(result,p,n-i))

      r[n]=q

      return r[n]

 

完整C++代码如下:

动态规划Dynamic Programming: Rod-Cutting Problem
 1 #include <iostream>
 2 
 3 
 4 using namespace std;
 5 
 6 
 7 //m is the total
 8 int cut(int* table, int n, int* r) {
 9     if (r[n-1]>=0) return r[n-1]; //r 存放切长度为n时的最优解,避免重复运算直接返回
10     if (n == 0) {
11         return 0;
12     } else {
13         //需要一个当前状态下最优解的临时参数存储
14         int temp = -9999;
15         for (int i = 1; i <= n; i++) {
16             int p_rest = cut(table,n-i,r);
17             if (temp < p_rest + table[i-1]) {
18               temp = p_rest+table[i-1];
19             }
20         }
21         r[n-1]=temp;
22         return r[n-1];
23     }
24 }
25 int main() {
26     int table[] = {1,5,8,9,10,17,17,20,24,30};
27 
28     int *result = new int[10];
29 
30     for (int i = 0; i < 10; i++) {
31      result[i] = -1;
32     }
33     
34     cout << cut(table,6,result) << endl;
35 
36     return 0;
37 }
动态规划Dynamic Programming: Rod-Cutting Problem

动态规划Dynamic Programming: Rod-Cutting Problem

上一篇:SlidingMenu(一)


下一篇:kvc、kvo、通知