정보 (및 수학) [정보 (및 수학)] [주말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

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

이 게시물을

번호	제목	글쓴이	날짜	조회 수
17	[화학] [인공지능] 세상에 없었던 신소재, AI가 찾는다…초전도체 소재도 찾을까	졸리운_곰	2023.11.30	196
16	[화학] [과학자가 해설하는 노벨상] 양자점 상용화...끝없는 질문에 답 찾는 과정	졸리운_곰	2023.10.16	226
15	[화학] [노벨상 2023] QLED TV에서 첨단의료까지…'양자점' 세상 연 3인, 화학상(종합)	졸리운_곰	2023.10.05	208
14	이산화탄소 자원화 ‘걸림돌’ 해결 실마리 찾았다	졸리운_곰	2020.11.22	218
13	소리로 화학반응 제어할 방법 나왔다	졸리운_곰	2020.08.16	216
12	아르키메디안 다면체의 자가조립(Self-assembly)	졸리운_곰	2015.10.01	363
11	최초의 디지털 코딩된 합성 고분자 개발	졸리운_곰	2015.06.09	414
10	거미줄 구조를 모방한 초강력 섬유 개발	졸리운_곰	2015.06.09	454
9	고통스러운 자극을 인지하는 신경세포의 기능을 조절하는 방법	졸리운_곰	2015.06.09	481
8	효율적인 비대칭 고리화 반응 연구	졸리운_곰	2015.06.07	416
7	원자와 탄소 표면 간의 상호작용을 더 정밀하게 측정할 수 있는 새로운 방법	졸리운_곰	2015.06.07	366
6	단일-사슬 나노입자	졸리운_곰	2015.05.31	284
5	전자 궤도 사이의 ‘전자 브리지’ 구축	졸리운_곰	2015.05.10	460
4	실리콘 태양전지의 성능을 매우 향상시키는 페로브스카이트	졸리운_곰	2015.01.20	265
3	`다이아몬드`라고 모두 영원한 것은 아니다	졸리운_곰	2014.05.31	477
2	화학산업에 혁명을 불러올 산화효소 구조 규명	가을의 곰을...	2013.12.18	3682
1	기록적인 성능을 가진 양자점 태양전지	가을의 곰을...	2013.09.20	5385

첫 페이지 1 끝 페이지

쓰기

태그

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

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

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

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

댓글 0

로그인

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