首页 > 代码库 > c++实现钢条切割问题
c++实现钢条切割问题
今天看了算法导论里面的动态规划(DP),有个有意思的问题:钢条切割来获取最大的收益。
书中讲到了几种求解方法,包括递归求解法、备忘录DP解法、自底向上的解法以及对解的重构。
书中给出不同解法的伪码,刚好需要练习c++,就有c++来实现DP求解钢条切割问题。
【递归求解】
// 钢条切割问题 // 自顶向下 递归实现 #include <iostream> #include <time.h> using namespace std; int cut_rod(int len, int price_arr[]); int main(int argc, char *argv[]) { clock_t start, finish; double duration; start = clock(); int rod_len = 10; int p_arr[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30}; int profit = cut_rod(rod_len, p_arr); cout << "profit = " << profit << endl; finish = clock(); duration = (double)(finish - start)/CLOCKS_PER_SEC; // 单位 s cout << "time cost = " << duration * 1000 << "ms" << endl; return 0; } /* 递归调用 cut_rod 函数 * input: 钢条长度len, 单位钢条长度价格表price_arr[] * output: 长度为len的钢条的最佳收益 * * 思想: * 1. 如果len==0,返回收益0 * 2. 否则,把钢条切割为左边长度为i 和右边长度为len-i 的两段, * 长度为i的一段不在切割,收益为price_arr[i], 右边部分继续分解。 * 注意: * 1. 程序存在访问风险;当输入长度大于 p_arr[]长度时,会访问到数组之外的元素; * 因此程序仅对 len < sizeof(p_arr)/sizeof(int) 的数据有效; */ int cut_rod(int len, int price_arr[]) { if (len == 0) return 0; int best_profit = -100; for (int i = 1; i <= len; i++) { best_profit = max(best_profit, price_arr[i] + cut_rod(len-i, price_arr)); } return best_profit; }
【自底向上DP重构解】
自底向上重构解包括自底向上求解法,因此在这儿只传重构的解法;
文章假定在钢条长度大于10英寸时,售价仍然为30美元,这样对输入的钢条长度就没有限制<当然这很不科学>;
/* DP 解决 钢条切割问题 * 不仅返回长度为len的钢条的最大收益r[],而且返回切割情况s[](重构的解) * 重构的解也是分析子问题的性质决定的 */ #include <iostream> #include <string.h> #define rod_len 17 #define LEN rod_len + 1 using namespace std; void extend_bottom_up_cut_rod(int len, int price_arr[], int (&r)[LEN], int (&s)[LEN]); void print_cut_rod_solution(int len, int price_arr[], int (&r)[LEN], int (&s)[LEN]); int main(int argc, char *argv[]) { int price[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30}; int r[LEN], s[LEN]; memset(r, 0, sizeof(r)); memset(s, 0, sizeof(s)); print_cut_rod_solution(rod_len, price, r, s); return 0; } void extend_bottom_up_cut_rod(int len, int price_arr[], int (&r)[LEN], int (&s)[LEN]) { if (len == 0) return; for (int j = 1; j <= len; j++) { int p = -1000; for (int i = 1; i <= j; i++) // 长度为j的钢条,切割i { int left_price; if (i > 10) left_price = price_arr[10]; else left_price = price_arr[i]; if (p < left_price + r[j-i]) { p = left_price + r[j-i]; s[j] = i; } } r[j] = p; } } void print_cut_rod_solution(int len, int price_arr[], int (&r)[LEN], int (&s)[LEN]) { extend_bottom_up_cut_rod(len, price_arr, r, s); cout << len << " inch rod price is " << r[len] << endl; cout << "the cut order is "; while (len > 0) { cout << s[len] << " "; len -= s[len]; } }
c++实现钢条切割问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。