# 自顶向上规划钢条切割

xiaoxiao2021-03-25  5

#include<iostream> #include<vector> using namespace std; void Init(vector<int> &p) { int n; int a; cout << "请输入价格表个数：" << endl; cin >> n; p.push_back(n);//将p的个数存在p[0]处 cout << "请输入各自的价格收益:" << endl; for (int i = 0; i < n; i++) { cin >> a; p.push_back(a); } } int max(int p, int q) { if (p >= q) { return p; } else return q; } int MEMOIZED_CUT_ROD_AUX(vector<int> &p, int n, int *r) { int q; if (r[n] >= 0) { return r[n]; } else { if (n == 0) { q = 0; } else { q = -1; for (int i = 1; i <= n; i++) { q = max(q, p[i] + MEMOIZED_CUT_ROD_AUX(p, n - i, r)); } r[n] = q; } } return q; } int MEMOIED_CUT_ROD(vector<int> &p, int *r,int n) { r = new int[n + 1]; for (int i = 0; i <= n; i++) { r[i] = -1; } return MEMOIZED_CUT_ROD_AUX(p,n,r); } void Delete(int *r) {//释放动态数组 delete[]r; } int main() { vector<int> p; int *r = NULL; int n; cout << "请输入要求的长度:" << endl; cin >> n; Init(p); cout << MEMOIED_CUT_ROD(p, r, n) << endl; Delete(r); system("pause"); return 0; } //此种方法仅仅是求出某一支路，然后由此构造出r[n]数组