상향식로드 컷 구현에 대한 이해

Introduction to Algorithms(CLRS)에서 Cormen et al. 다음과 같이 (페이지 369)를로드 절단 문제를 해결에 대해 이야기 여기상향식로드 컷 구현에 대한 이해

EXTENDED-BOTTOM-UP-CUT-ROD(p, n) 
    let r[0...n] and s[0....n] be new arrays 
    r[0] = 0 

    for j = 1 to n: 
     q = -infinity 

     for i = 1 to j: 
      if q < p[i] + r[j - i]: // (6) 
       q = p[i] + r[j - i] 
       s[j] = i 
     r[j] = q 

    return r and s

p[i]이 길이 난을로드를 절단의 가격은, r[i] 길이 i와 s[i]에서로드를 절단의 수익이, 우리를 제공합니다 첫 번째 조각이 잘리는 최적의 크기.

내 질문 n에 1에서 j을 반복 할 외부 루프뿐만 아니라 1에서 n에 간다 내부 루프 i에 관한 것입니다.

온라인으로 (지금까지 얻은 최대 수익)을 r[j - i] (이전 커트 동안 얻은 최대 수익)과 비교합니다.

j = 1 and i = 1 일 때, 내부 루프의 다음 반복은 괜찮은 것 같습니다. 여기서 j = 1 and i = 2은 r[j - i] be r[1 - 2] = r[-1]이 아니겠습니까?

음수 인덱스가 여기에 적합한 지 확실하지 않습니다. CLRS의 오타입니까? 아니면 여기에 뭔가 빠졌습니까?

혹시 막대 절단 문제가 무엇인지 모르시겠습니까? 여기에 example입니다. for i = 1 to j

i는 1에서 시작하고 값 까지하지만j의 값을 초과하지 않는 증가합니다

출처

2011-03-31 sc_ray

여기에 키입니다.

i은 결코 j보다 크지 않으므로 j-i은 절대로 0보다 작지 않습니다.

출처

2011-03-31 22:51:07 Unsigned

코드 연구소 - 예. 어리석은 감시. 그 점을 지적 해 주셔서 감사합니다. –

문제 없습니다, 우리 모두 가끔 때때로 간과합니다 :) – Unsigned

변수 i는 내부 루프 때문에 변수 j보다 크지 않으므로 인덱스 r은 결코 0보다 작아지지 않습니다.

출처

2011-03-31 22:55:59 Bytemain

inner for 루프의 조건이 누락되었습니다. 그 점에서, i의 가치는 오직 최대로갑니다. 따라서 j를 초과하면 루프가 종료됩니다. 따라서 당신이 언급 한 부정적인 지수에 대해서는 의문의 여지가 없습니다.

출처

2014-11-19 17:17:42 kpks

상향식로드 컷 구현에 대한 이해

답변

관련 문제