- 채우는 중
- 읽는 칸
- 답
배낭 문제
들 수 있는 무게는 한정되어 있고, 물건마다 무게와 가치가 있습니다. 가장 큰 가치를 가져가려면 어떤 물건을 골라야 할까요? 모든 조합을 시도하면 물건이 하나 늘 때마다 작업량이 두 배가 됩니다. 물건을 행으로, 용량을 열로 하는 표는 한 칸씩 최선의 배낭 구성을 찾아냅니다. 물건을 탭하면 배낭에 넣고, 다시 탭하면(배낭 안이든 선반 위든) 뺍니다. 배낭은 무게만큼 차고, 타일에는 담은 달러가 가능한 최대 가치와 함께 표시됩니다. 최적 담기를 누르면 가장 좋은 배낭을 볼 수 있습니다. 패널에서 물건의 킬로그램과 달러를 바꾸고, 물건을 추가하거나 삭제하고, 배낭 용량을 정하세요. 표 보기는 동적 계획법이 가장 좋은 배낭을 찾는 방법을 보여 줍니다. 재생을 누르면 표가 채워지는 과정을 볼 수 있고, 단계와 뒤로 버튼으로 한 단계씩 움직일 수 있으며, 단계 슬라이더를 끌면 원하는 곳으로 바로 이동합니다. 각 행은 물건을 하나 추가하고, 각 열은 킬로그램 단위의 용량이며, 각 칸에는 들어갈 수 있는 최대 달러가 들어갑니다. 표를 선택한 상태에서 화살표 키는 한 단계씩 이동하고, 스페이스 바는 재생과 일시 정지를, Home과 End 키는 처음과 끝으로 이동합니다.
작동 원리
- 물건 상자를 눌러 배낭에 담고, 배낭이 킬로그램 무게만큼 채워지는 모습을 확인하세요.
- 달러로 가능한 최고의 가치를 만들어 보거나, 최적 담기을(를) 눌러 가장 좋은 배낭을 확인하세요.
- 표 보기를 열고 재생을 눌러 각 칸이 물건을 담을지 뺄지 고르는 과정을 지켜보세요.
표가 작동하는 방식
각 행은 물건을 하나씩 추가하고, 각 열은 0부터 배낭의 용량까지의 용량입니다. 칸에는 그 행까지의 물건을 사용해 그 용량에 들어갈 수 있는 최대 가치가 담깁니다. 새 물건을 쓰지 않으면 그 값은 위 칸입니다. 새 물건을 쓰면, 그 물건이 들어갈 경우, 물건의 가치에 남은 무게에 대한 최대 가치를 더한 값이며, 이 값은 위 행에서 물건의 무게만큼 왼쪽에 있습니다. 칸은 둘 중 큰 값을 가집니다. 물건이 없는 첫 행은 모두 0입니다.
물건 거꾸로 읽기
오른쪽 아래 칸이 최대 가치입니다. 물건을 찾으려면 거기서 시작해 위 칸과 비교하세요. 같으면 마지막 물건은 필요 없었던 것이고, 더 크면 그 물건은 배낭에 있으므로 그 무게를 빼고 해당 열로 이동합니다. 첫 행에 닿을 때까지 매번 한 행씩 올라갑니다. 앱은 이 거꾸로 읽기를 주황색으로 보여 주고, 담은 물건을 표 아래에 나열합니다.
자주 묻는 질문
0/1 배낭 문제에서 0/1은 무슨 뜻인가요?
각 물건은 한 번 넣거나 아예 넣지 않으며, 일부만 넣거나 두 번 넣을 수 없습니다. 쌀알처럼 물건을 나눌 수 있다면 무게당 가치가 가장 높은 것부터 넣는 것이 최적이며, 이것을 분할 가능 배낭 문제라고 합니다.
왜 무게당 가치가 가장 높은 물건부터 넣지 않나요?
통째로 넣는 물건은 빈틈을 남길 수 있기 때문입니다. 용량이 7이고 무게가 1, 3, 4, 5, 가치가 1, 4, 5, 7인 물건이 있을 때, 무게당 가치가 가장 높은 것은 무게 5인 물건인데, 그것을 넣으면 무게 1인 물건이 들어갈 자리만 남아 합계가 8입니다. 무게 3과 4인 물건을 함께 넣으면 가치가 9입니다.
배낭 알고리즘은 얼마나 빠른가요?
표에는 (물건 수 + 1) × (용량 + 1)개의 칸이 있고, 각 칸은 한 단계에 채워집니다. 용량이 작으면 빠르지만 용량은 아주 큰 수일 수 있으므로, 이 문제는 일반적으로 NP-난해입니다. 이런 표 방식을 의사 다항 시간 알고리즘이라고 합니다.
같은 물건을 두 번 넣을 수 있나요?
여기서는 안 됩니다. 무제한 배낭 문제에서는 각 물건을 몇 번이든 고를 수 있으며, 이때 표는 동전 교환 앱에서처럼 위 행 대신 같은 행의 왼쪽 칸을 읽습니다.
데이터가 어딘가로 전송되나요?
아니요. 모든 계산은 브라우저에서 이루어지고, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동