Fundamental Algorithms Analysis(008)-Cut Rod[강철 막대 절단 문제/정장 분배][C++/Java]
Plain recursive method
int cutRod(map<int,int> list,int n) {
if (n == 0) return 0;
int q = INT_MIN;
for (int i = 1; i <= n; ++i) q = max(q, list[i] + cR1(list,n - i));
return q;
}
Improved recursive
I like search in table.시 계 를 찾 는 것 이 더 빠 를 것 입 니 다!
vector<int> table(99999, INT_MIN);
int cutRod(map<int, int> list, int n) {
if (table[n] >= 0) return table[n];// If exists, search from table
if (n == 0) return table[0] = 0;
int q=INT_MIN;
for (int i = 1; i <= n; ++i)q = max(q, list[i] + cutRod(list, n - i));
return table[n]=q;//Store new value
}
Dynamic Programming method
Still table! 시 계 를 끝까지 조사 하 라!
vector<int> table(99999,0);
int cutRod(map<int, int> list, int n) {
for (int i = 1; i <= n; ++i) {
int q = INT_MIN;
for (int j = 1; j <= i; ++j) q = max(q, list[j] + table[i - j]);
table[i] = q;
}
return table[n];
}
Main test(C++)
#include
#include
#include
#include
using namespace std;
int cR1(map<int,int> list,int n) {
if (n == 0) return 0;
int q = INT_MIN;
for (int i = 1; i <= n; ++i) q = max(q, list[i] + cR1(list,n - i));
return q;
}
vector<int> table1(99999, INT_MIN);
int cR2(map<int, int> list, int n) {
if (table1[n] >= 0) return table1[n];// If exists, search from table
if (n == 0) return table1[0] = 0;
int q=INT_MIN;
for (int i = 1; i <= n; ++i)q = max(q, list[i] + cR2(list, n - i));
return table1[n]=q;//Store new value
}
vector<int> table2(99999, 0);
int cR3(map<int, int> list, int n) {
for (int i = 1; i <= n; ++i) {
int q = INT_MIN;
for (int j = 1; j <= i; ++j) q = max(q, list[j] + table2[i - j]);
table2[i] = q;
}
return table2[n];
}
int main() {
map<int, int> list{ {1,1},{2,5},{3,8},{4,9},{5,10},{6,17},{7,17},{8,20},{9,24},{10,30} };
cout<<cR3(list, 7);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu 1717 소수 화 점수 2 (수학)소수 화 점수 2 레이 는 수학 시간 에 선생님 의 말씀 을 듣 고 모든 소수 가 점수 로 표시 되 는 형식 이 라 고 말 했다. 그 는 녹 기 시 작 했 고 곧 완성 되 었 다. 그러나 그 는 또 하나의 문 제 를...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.