탐욕적 선택 속성 O, 최적 부분 구조 X 인 예가 있을까요?

  • 박요한
    박요한

    JM북을 공부 중입니다. '10.1 탐욕법 도입' 부분(p.369)을 보면, 최적 부분 구조를 설명 하는 부분에서
    "(탐욕적 선택 속성이 증명 되었어도, 최적 부분 구조는) 경우에 따라 성립하지 않는 경우도 있습니다. 첫 번째 선택을 하고 나서 남는 부분 문제는 최적이 아닌 방법으로 풀어야 하는 경우죠."
    라는 설명이 나옵니다.

    탐욕적 선택 속성이 성립하지만 최적 부분 구조는 성립하지 않는 경우로 어떤 예가 있을까요?

    고수님들의 도움을 기다립니다..


    7년 전
0개의 댓글이 있습니다.

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.