온라인 배낭 문제 해결사

온라인 배낭 문제 해결사

정수 무게와 용량으로 0/1 배낭 문제를 풀고 총가치가 최대인 선택 한 가지를 구합니다.

한 줄에 이름,무게,가치를 ASCII 쉼표로 구분해 입력하세요. 이름은 앞뒤 공백 제거 후 비어 있지 않고 고유해야 하며 쉼표를 포함할 수 없습니다. 각 필드 주변 공백은 허용하고 빈 줄은 무시합니다. 가치의 소수 구분자는 점입니다.

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

아래 세 줄을 붙여 넣고 별도 용량 칸에 5를 입력해 계산하세요. 최대 가치 16, 선택 A, B입니다. 복사는 결과를 복사하며 지우기는 용량도 비웁니다.

물품 1~200개, 용량은 1~5000 정수, 무게는 1부터 용량까지 정수, 가치는 비어 있지 않은 0~1000000000의 유한 수이며 소수도 허용합니다. 용량 초과 물품 하나가 있으면 전체 입력을 거부합니다. 텍스트 한도는 UTF-16 코드 단위 500000개입니다. 각 물품은 최대 한 번만 선택합니다. 최대 가치와 이름만 표시하며 총무게는 표시하지 않습니다. 값이 정확히 같으면 뒤쪽 물품을 건너뛰므로 입력 순서에 따라 선택된 최적 조합이 달라질 수 있습니다. 최소 무게를 우선하지 않습니다. 가치가 모두 0이면 결과는 0과 빈 선택입니다. 소수 연산은 반올림될 수 있으므로 정확한 금액은 정수 단위로 바꾸세요.