0/1 배낭 항목 선택

각 항목의 정수 무게와 가치로 용량 안에서 가치 합이 가장 큰 선택을 찾으세요.

예시값이 입력되어 있습니다. 바로 확인하거나 값을 바꿔 보세요.

입력은 브라우저에서 처리합니다. 새로고침하면 예시값으로 돌아갑니다.

결과

사용 방법과 예시

DPᵢ(c)=max(DPᵢ₋₁(c),DPᵢ₋₁(c−wᵢ)+vᵢ); xᵢ∈{0,1}

무게·가치 2,3 / 3,4 / 4,5에서 용량 5이면 행 1,2를 골라 무게 5, 가치 7입니다.

최대 100항목, 정수 무게 1~10,000·가치 0~1,000,000·용량 0~10,000입니다. 반복 구매와 항목 분할은 허용하지 않습니다. 부동소수점 결과는 최대 유효숫자 12자리로 표시합니다.

자주 묻는 질문

같은 물건을 여러 개 선택하려면 어떻게 하나요?

수량만큼 별도 행으로 입력하세요. 각 행은 한 번만 선택되며 이름이 아닌 행 번호로 결과를 표시합니다.

배낭의 용량을 꼭 채워야 하나요?

아니요. 용량 이하에서 가치 합을 최대화합니다. 남는 용량이 있어도 최적일 수 있습니다.

계산 기준과 참고 자료

계산 기준 확인: · 계산·검증 원칙 · 오류 제보