분기 한정법과 배낭 문제

안녕하세요! 이제 수업을 거의 다수강해 가고 있네요. 감사합니다!

그런데 분기 한정법과 배낭 문제에 몇가지 질문할 것이 있습니다.

첫번째,

bound : 현재 노드에서 앞으로 얻을 수 있는 최대 이익

이라고 하셨는데, 

이 식을 보면

(bound = (현재까지 얻은 이익+나머지 노드들 중 전부 담아도 W를 넘지 않는 이익) + (전부 담으면 W가 넘는 노드 k의 이익))

로 이해가 됩니다.

그런데, w_i배열의 마지막 값이 앞선 원소들의 합보다 월등히 크다면,

위 bound 식이 현재 노드에서 앞으로 얻을수 있는 최대 이익이 될 수 없을 것 같습니다.

그래서 제 생각에는 먼저 이익의 내림차순으로 정렬을 하면 bound의 정의를 만족할 것 같은데 제각 생각한것이 맞을까요?

두번째,

,   

위 두 그림에서 (3,1)과 (4,1)이 nonpromising한 이유가 bound 값이 maxprofit보다 작아서 라고 하셨는데,

제 생각에는 (bound = (현재까지 얻은 이익+나머지 노드들 중 전부 담아도 W를 넘지 않는 이익) + (전부 담으면 W가 넘는 노드 k의 이익)) 인데, 그렇다면 항상 (3,1)과 (4,1)에서의 bound 값은 maxprofit보다 크거나 같을 것 같습니다.

그래서 제 생각에는 nonpromising한 이유가 bound 값 때문이 아니라 무게의 합이 W보다 거쳐서 nonpromising 하다고 생각했는데 맞을까요?

항상 강의 잘 듣고 있습니다.

좋은강의에 늘 감사드립니다 :)