온라인 배낭 문제 해결사

0/1 배낭 문제란?

0/1 배낭 문제는 각 항목을 최대 한 번만 선택할 수 있는 조합 최적화 문제입니다. 주어진 용량 내에서 가치의 합을 최대화하는 항목 집합을 찾습니다.

작동 방식

이 도구는 동적 프로그래밍 알고리즘을 사용하여 최적해를 계산합니다. 입력된 항목과 용량을 기반으로 모든 가능한 조합을 효율적으로 탐색합니다.

구체적인 예

예를 들어, 다음 항목이 있다고 가정합니다:

A,2,6
B,3,10
C,4,12

용량이 5일 때, 최대 가치는 16이며 선택된 항목은 A와 B입니다.

제한 사항

• 이 도구는 0/1 배낭 문제만 지원합니다. 분할 가능, 다중 제한, 다차원 또는 통화 인식 배낭 문제는 지원하지 않습니다.
• 동일한 가치를 가진 여러 선택이 있는 경우, 모든 경우를 나열하지 않으며 최적 선택 하나만 표시합니다.
• 가치는 추상적인 점수로 처리됩니다. 사용자가 직접 단위를 정규화하지 않는 한 통화나 특정 단위로 해석하지 마십시오.

자주 묻는 질문

항목 이름에 공백이나 특수 문자를 사용할 수 있나요?

항목 이름은 비어 있지 않고 고유해야 합니다. 공백이나 특수 문자는 허용되지만, 쉼표는 구분자로 사용되므로 이름에 포함할 수 없습니다.

무게가 용량보다 큰 항목은 어떻게 처리되나요?

무게가 용량보다 큰 항목은 선택될 수 없으므로 결과에 포함되지 않습니다. 입력 시 오류가 발생할 수 있습니다.

결과가 항상 최적해인가요?

네, 동적 프로그래밍 알고리즘은 항상 최적해를 찾습니다. 그러나 동일한 가치의 다른 선택이 존재할 수 있으며, 이 도구는 그 중 하나만 표시합니다.