1:1 최소 비용 배정

담당자와 작업의 정사각 비용 표에서 중복 없는 전체 배정과 최소 비용을 찾으세요.

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

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

결과

사용 방법과 예시

DP(mask∪{j})=min(DP(mask)+cost[popcount(mask),j])

기본 비용 표의 최적 배정은 1→2, 2→1, 3→3이며 합계는 2+6+1=9입니다.

1~10행의 정사각 행렬, 비용 0~1,000,000 정수입니다. 모든 행·열을 정확히 배정하며 금지 배정·용량·선후 관계는 다루지 않습니다. 부동소수점 결과는 최대 유효숫자 12자리로 표시합니다.

자주 묻는 질문

배정 비용 0은 금지를 뜻하나요?

아니요. 0은 비용 없는 허용 배정입니다. 금지할 조합이 있으면 이 모델 범위에 맞지 않습니다.

담당자 수와 작업 수가 다르면 어떻게 되나요?

직사각형 입력은 거부합니다. 빈 자리의 의미와 비용을 검토한 뒤 명시적인 더미 행·열을 직접 추가할 수 있습니다.

계산 기준과 참고 자료

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