정보 (및 수학) [정보 (및 수학)] [주말N수학] 설레는 휴가철…효율적인 짐 싸기 위한 '배낭 문제'

2024.06.01 15:34

[정보 (및 수학)] [주말N수학] 설레는 휴가철…효율적인 짐 싸기 위한 '배낭 문제'

[주말N수학] 설레는 휴가철…효율적인 짐 싸기 위한 '배낭 문제'

입력2024.06.01. 오전 8:00

게티이미지뱅크 제공

여행을 떠나기 전 짐을 싸는 건 여간 귀찮은 일이 아니다. 생각나는 대로 짐을 챙기다 보면 짐이 가방에 다 들어가지 않아 난감할 때도 있다. 그런데 수많은 짐 중 어떤 것부터 골라서 싸야 하는지 알려주는 수학 이론이 있다. 바로 '배낭 문제'다.

배낭 문제란 넣을 수 있는 물건의 총량이 제한된 배낭에 가치의 합이 최대가 되도록 물건을 담는 조합 최적화 문제다. 이때 선택한 물건들의 무게 합은 주어진 최대 무게를 초과하면 안 된다. 배낭 문제는 단순해보이지만, 모든 경우의 수를 직접 확인해봐야 해서 답을 구하기가 어렵다.

최대 용량이 10kg인 배낭에 다음과 같은 짐을 담는 상황을 생각해보자. 배낭 문제를 통해 배낭에 담는 물건의 합이 10kg 이하가 되면서 물건 가치의 합은 최대가 되는 경우를 찾을 수 있다. 여기에는 무게순, 가치순, 무게당 가치순으로 배낭을 꾸리는 세 가지 방법이 있다.

(왼쪽 방법1부터)무게가 무거운 짐부터 배낭을 꾸리면 배낭에는 쌀, 여벌 옷, 음료수, 손전등을 담을 수 있다. 이때 가치의 합은 18점이다, 가치가 높은 것부터 배낭을 꾸리면 배낭에는 구급약, 음료수, 쌀, 손전등까지 담을 수 있다. 이때 가치의 합은 19점이다, 무게당 가치가 높은 것부터 배낭을 꾸리면 배낭에는 쌀을 제외하고 모두 담을 수 있다. 이때 가치의 합은 24점이다. 수학동아 제공

위의 세 가지 방법 중 '방법 3'으로 배낭을 꾸릴 때 가치의 합이 최대가 된다. 하지만 이 방법 역시 모든 물건을 넣을 수는 없다. 이는 우리가 '0-1 배낭 문제' 를 풀었기 때문이다. 0-1 배낭 문제는 짐을 넣거나 빼거나 둘 중 하나만 선택하는 문제다.

모든 짐을 조금씩 가져가고 싶다면 짐을 쪼개서 가져갈 수 있는 '분할 가능 배낭 문제'를 이용하면 된다. 0-1 배낭 문제는 이를 풀기 위한 가장 효과적인알고리듬이 알려져 있지 않아 여러 조합을 탐색해봐야 하는 반면 분할 가능 배낭 문제는 그리디 알고리즘(여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 근사적으로 최적의 해를 구하는 데 쓰이는 방법)으로 해결할 수 있다.

수학동아 편집부

[출처] https://n.news.naver.com/article/584/0000027341?cds=news_media_pc

경축! 아무것도 안하여 에스천사게임즈가 새로운 모습으로 재오픈 하였습니다.
어린이용이며, 설치가 필요없는 브라우저 게임입니다.
https://s1004games.com

본 웹사이트는 광고를 포함하고 있습니다.
광고 클릭에서 발생하는 수익금은 모두 웹사이트 서버의 유지 및 관리, 그리고 기술 콘텐츠 향상을 위해 쓰여집니다.

이 게시물을

번호	제목	글쓴이	날짜	조회 수
13	[지구과학] [표지로 읽는 과학] 고대 산호초로 보는 엘니뇨의 미래	졸리운_곰	2024.02.04	223
12	[지구과학] 나무 막대기 하나로 알아낸 지구의 크기	졸리운_곰	2024.01.14	230
11	[지구과학] [표지로 읽는 과학] [표지로 읽는 과학] 돌로마이트, 고대엔 풍부했지만 실험실 제조는 어려워	졸리운_곰	2023.11.26	232
10	[지구과학] [표지로 읽는 과학] 45억 년 전 원시 지구 '거대한 충돌'의 증거	졸리운_곰	2023.11.04	185
9	[환경] "온실가스 배출 감소만으로 기후변화 못 막는다"	졸리운_곰	2023.11.03	281
8	[지구과학] 원시 행성 '테이아', 지구 내부에 대륙 크기 흔적 남겼다	졸리운_곰	2023.11.02	230
7	[지구과학] “공룡은 단 1분 차이로 멸종했다”	졸리운_곰	2023.10.31	208
6	[지구과학] 6600만년 전 공룡 멸종시킨 소행성은 태양계 가장 먼 곳에서 날아왔다	졸리운_곰	2023.10.31	184
5	[지구과학] 소행성 충돌로 인한 엄청난 미세먼지 '공룡 멸종' 불렀다	졸리운_곰	2023.10.31	130
4	[환경] 평균기온 1도 더 오르면 40억명이 견디기 힘든 더위 겪는다	졸리운_곰	2023.10.10	234
3	[지구과학] 강진 발생한 모로코 상공에 나타난 '빛' 미스터리	졸리운_곰	2023.09.13	237
2	[환경] 남극에 '에어로졸' 뿌려 온난화 예방?..."근본적 해결책 아냐"	졸리운_곰	2023.08.15	227
1	[환경] 美, 탄소 빨아들이는 '거대한 선풍기' 만든다	졸리운_곰	2023.08.13	217

첫 페이지 1 끝 페이지

쓰기

태그

정보 (및 수학) [정보 (및 수학)] [주말N수학] 설레는 휴가철…효율적인 짐 싸기 위한 '배낭 문제'

[정보 (및 수학)] [주말N수학] 설레는 휴가철…효율적인 짐 싸기 위한 '배낭 문제'

[주말N수학] 설레는 휴가철…효율적인 짐 싸기 위한 '배낭 문제'

경축! 아무것도 안하여 에스천사게임즈가 새로운 모습으로 재오픈 하였습니다. 어린이용이며, 설치가 필요없는 브라우저 게임입니다. https://s1004games.com

댓글 0

로그인

경축! 아무것도 안하여 에스천사게임즈가 새로운 모습으로 재오픈 하였습니다.
어린이용이며, 설치가 필요없는 브라우저 게임입니다.
https://s1004games.com