- 전체
- 물리
- 천체물리 - 우주(과학)
- 정보 (및 수학)
- 화학
- 생물 및 의학 (건강)
- 전기전자
- 지구과학 and 환경
- 사회과학
- 기계
- ITFIND 주간 기술 동향
- 월간 ICT 동향
- 인문학(과학)
정보 (및 수학) [정보 (및 수학)] [주말N수학] 설레는 휴가철…효율적인 짐 싸기 위한 '배낭 문제'
2024.06.01 15:34
[정보 (및 수학)] [주말N수학] 설레는 휴가철…효율적인 짐 싸기 위한 '배낭 문제'
[주말N수학] 설레는 휴가철…효율적인 짐 싸기 위한 '배낭 문제'
입력2024.06.01. 오전 8:00
배낭 문제란 넣을 수 있는 물건의 총량이 제한된 배낭에 가치의 합이 최대가 되도록 물건을 담는 조합 최적화 문제다. 이때 선택한 물건들의 무게 합은 주어진 최대 무게를 초과하면 안 된다. 배낭 문제는 단순해보이지만, 모든 경우의 수를 직접 확인해봐야 해서 답을 구하기가 어렵다.
최대 용량이 10kg인 배낭에 다음과 같은 짐을 담는 상황을 생각해보자. 배낭 문제를 통해 배낭에 담는 물건의 합이 10kg 이하가 되면서 물건 가치의 합은 최대가 되는 경우를 찾을 수 있다. 여기에는 무게순, 가치순, 무게당 가치순으로 배낭을 꾸리는 세 가지 방법이 있다.
모든 짐을 조금씩 가져가고 싶다면 짐을 쪼개서 가져갈 수 있는 '분할 가능 배낭 문제'를 이용하면 된다. 0-1 배낭 문제는 이를 풀기 위한 가장 효과적인알고리듬이 알려져 있지 않아 여러 조합을 탐색해봐야 하는 반면 분할 가능 배낭 문제는 그리디 알고리즘(여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 근사적으로 최적의 해를 구하는 데 쓰이는 방법)으로 해결할 수 있다.
수학동아 편집부
[출처] https://n.news.naver.com/article/584/0000027341?cds=news_media_pc
본 웹사이트는 광고를 포함하고 있습니다.
광고 클릭에서 발생하는 수익금은 모두 웹사이트 서버의 유지 및 관리, 그리고 기술 콘텐츠 향상을 위해 쓰여집니다.
광고 클릭에서 발생하는 수익금은 모두 웹사이트 서버의 유지 및 관리, 그리고 기술 콘텐츠 향상을 위해 쓰여집니다.
