물건을 나눌 수 있는 배낭과 나눌 수 없는 배낭에서 가치 비율 탐욕법의 정당성은 왜 달라지나요?

꼬리 질문을 독립 문항으로 확장했습니다. 원래 문항에서 맥락 보기 →

잠깐, 답변을 보기 전에
먼저 내 말로 설명해 볼까요?

답변과 점검 포인트 펼치기답변 접기

구두 답변

정의를 외우기보다, 원리와 조건을 연결해 설명해 보세요.

분할 가능한 배낭은 높은 가치/무게 비율을 먼저 담고 마지막 물건 일부를 넣을 수 있어 교환 논증이 성립합니다. 0-1 배낭은 물건을 쪼갤 수 없어 비율이 좋은 선택이 남은 공간을 비효율적으로 만들 수 있습니다.

용량 50, (무게,가치)=(10,60),(20,100),(30,120)이면 비율 탐욕은 첫 둘의 160을 고르지만 뒤 둘은 220입니다. DP의 상태·용량 범위와 의사 다항 비용을 확인합니다. 입력 제약 없는 탐욕 일반화는 하지 않습니다.

이해가 드러나는 지점을 확인해 보세요.

분할 가능한 배낭은 높은 가치/무게 비율을 먼저 담고 마지막 물건 일부를 넣을 수 있어 교환 논증이 성립합니다. 0-1 배낭은 물건을 쪼갤 수 없어 비율이 좋은 선택이 남은 공간을 비효율적으로 만들 수 있습니다.
입력 제약 없는 탐욕 일반화는 하지 않습니다.

놓치기 쉬운 조건과 오해를 짚어 보세요.

다음 핵심 구분을 반대로 설명하거나 성립 조건을 생략한다: 분할 가능한 배낭은 높은 가치/무게 비율을 먼저 담고 마지막 물건 일부를 넣을 수 있어 교환 논증이 성립합니다.

하나 더 질문하며 이해의 범위를 넓혀 보세요.

득점·감점 포인트는 학습용 자기 점검 기준이며, 특정 회사의 실제 채점표가 아닙니다.

답변을 보충하는 개념·예제·슈도코드를 읽어 보세요.