배낭 상한

Question

나는 문제는 knappsack에 관심이 있고 분기와 바운드 알고리즘으로 해결하고 싶다.

값/중량 비율로 내림차순 1..n 항목을 정렬하고 배킹 항목 s (배낭에 완전히 들어 가지 않는 첫 번째 항목)를 찾고 다음을 계산하여 상한값을 계산할 수 있음을 알고 있습니다. :

(C는 승 Knappsack, (j)의 j 번째 아이템의 중량 용량)

(여전히 knappsack에 맞는 S의 비율을 계산)

(합계 첫 번째 s-1 항목의 모든 값을 올리고 값의 일부를 더합니다. ue of)

그러나 내가 이해할 수없는 것은 우리가 여전히 상한을 유지하고있는 세 번째 방정식의 두 번째 부분을 반올림 할 수있는 이유입니다.

누군가가 나에게 힌트, 설명 또는 그것을 설명하는 참고 문헌을 제공하기를 바랍니다.

Answer 1

모든 문항에는 정수 값이 있다고 가정합니다. 이 경우 최대 값은 정수이므로 분명히 상한은 정수로 반올림 될 수 있습니다.

값이 실수 인 경우 반올림이 올바르지 않음