널빤지 절단 문제(二)-동적 기획
길이가 L(L < 1000)인 나무 막대기와 n(n < 50)개의 절단점 위치(작은 것부터 큰 것까지)가 있다.너의 임무는 이 절단점의 위치에서 막대기를 n+1부로 잘라서 총 비용을 최소화하는 것이다.매번 절단하는 비용은 절단된 나무 막대기의 길이와 같다.
2. 문제 분석
이 문제는 앞의 울타리 수리(n개의 막대기의 길이를 정하고 절단점을 임의로 정하는 것)와 비슷하다. 이 문제는 n+1개의 막대기의 길이를 정하고 절단점을 고정시키는 것과 같다.이전의 욕심법은 적용할 수 없다. 욕심법으로 절단해야 할 점이 반드시 주어진 절단점이 아니기 때문이다.우리는 반드시 사고방식을 바꾸어야 한다.
n의 규모는 매우 작아서 매거 절단점을 고려할 수 있지만 모든 절단 순서를 직접 매거하는 것은 너무 커서 동태적인 계획을 고려하고 매거 절단의 첫 번째 칼의 위치를 고려할 수 있다.
d(i,j)를 작은 나무 막대기 i~j를 절단하는 최우선 비용으로 설정하면 d(i,j)=min{(d(i,k),d(k,j))|i
3. 코드 실현
1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6
7 const int INF = 0x3f3f3f3f;
8 const int maxl = 1000 + 10;
9 const int maxn = 50 + 10;
10 int L, n, cutp[maxn];
11 int d[maxn][maxn]; //d[i][j] i-->j ,i,j ，d[0][n + 1]
12
13 void slove()
14 {
15 for (int i = n + 1; i >= 0; i--) // ，
16 for (int j = i; j <= n + 1; j++) // ，
17 {
18 d[i][j] = (i + 1 == j ? 0 : INF);
19 for (int k = i + 1; k < j; k++)
20 d[i][j] = min(d[i][j], d[i][k] + d[k][j] + cutp[j] - cutp[i]);
21 }
22 printf("The minimum cutting is %d.
", d[0][n + 1]);
23 }
24
25 int main()
26 {
27 while (scanf("%d", &L) == 1 && L)
28 {
29 scanf("%d", &n);
30 for (int i = 1; i <= n; i++)
31 scanf("%d", &cutp[i]);
32
33 // 0， n + 1
34 cutp[0] = 0; cutp[n + 1] = L;
35
36 slove();
37 }
38 return 0;
39 } 4. 총결산
이런 해법은 상태에 O(n2)가 있고 각 상태에 O(n)개의 결정이 있으며 시간 복잡도는 O(n3)이다.사각형 부등식으로 O(n2)까지 최적화할 수 있다고 하니 나중에 만나서 보충합시다.
전재 대상:https://www.cnblogs.com/lfri/p/9458060.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
