钢条切割-【算法导论-动态规划】

#include <iostream> using namespace std; int max(int a, int b) { return a > b ? a : b; } int cut(int *value, int count, int length) { int *r = new int[length + 1]; int q; r[0] = 0; for(int j = 1; j <= length; j++) { q = -1; for(int i = 1; i <= j; i++) { if(i <= count) q = max(q, value[i] + r[j - i]); else q = max(q, r[i] + r[j - i]); } r[j] = q; } return r[length]; } int main() { int count = 0; cout << "请输入钢条的长度：" << endl; cin >> count; int *value = new int[count + 1]; for(int i = 1; i <= count; i++) cin >> value[i]; cout << "请输入此时钢条长度" << endl; int length = 0; cin >> length; cout << "最大利益为" << cut(value, count, length) << endl; return 0; }