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

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

이 게시물을

번호	제목	글쓴이	날짜	조회 수
39	[전기/전자] 2037년에서야 가능한줄 알았는데…국내 연구진, 초미세 반도체 구현 성공	졸리운_곰	2024.07.04	238
38	[전기/전자] [사이언스 게시판] KAIST, '성능 극대화' 리튬금속전지 전해액 기술 개발 (이차전지 뉴스)	졸리운_곰	2023.10.05	255
37	[전기/전자] 반도체·금속 성질 모두 갖는 새 나노입자 개발	졸리운_곰	2023.09.23	215
36	[전기전자] 빛으로 작동하는 '다진법 메모리' 가능성 열었다	졸리운_곰	2023.09.21	320
35	[전기전자] AI로 수소연료전지 촉매 개발…성공률·속도 획기적으로 높였다	졸리운_곰	2023.09.07	157
34	[전기,전자] 꿈의 신소재 '맥신', 대량생산 길 열렸다	졸리운_곰	2023.08.18	152
33	[랩큐멘터리]구글·인텔도 뛰어든 양자컴퓨터 세계로 '퀀텀점프'	졸리운_곰	2021.02.01	167
32	높은 인성 및 전기 전도성을 가진 새로운 탄소 나노튜브 구조	졸리운_곰	2017.05.05	271
31	양자전산의 오류를 제거할 하드웨어를 개발하는 IBM	졸리운_곰	2016.01.31	330
30	레이저 프로젝터에 영감을 받은 새로운 칩 기술	졸리운_곰	2016.01.31	337
29	나노 탄소 재료 로드 금속 촉매 연구	졸리운_곰	2016.01.31	272
28	4G 데이터 연결 기능을 제공하는 새로운 기술 개발	졸리운_곰	2015.10.01	269
27	SSD 표준 규격, 4년 만에 갱신	졸리운_곰	2015.09.27	269
26	빛으로 전력을 생산하는 새로운 배터리 개발	졸리운_곰	2015.09.27	333
25	NRAM의 조기 실용화 목표	졸리운_곰	2015.09.27	259
24	전자 현미경 이용해 반도체 pn 접합의 계면 전기장 관찰 성공	졸리운_곰	2015.09.27	722
23	사용자용 가상현실 헤드셋 장치 개발	졸리운_곰	2015.09.27	263
22	포논 충돌 간의 거리를 계산하는 툴	졸리운_곰	2015.06.09	463
21	고용량 축전지의 소스가 되는 목재	졸리운_곰	2015.06.07	241
20	매우 효율적인 광학 기반 컴퓨터	졸리운_곰	2015.06.07	268

첫 페이지 1 2 끝 페이지

쓰기

태그

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

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

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

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

댓글 0

로그인

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