#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]数组
转载请注明原文地址: https://ju.6miu.com/read-200268.html
