【와티비커뮤니티-WATVcommunity】 보증업체놀이터추천홍보 : 프로그램제작판매제작의뢰 : 스포츠분석 : 무료스포츠중계tv : 섹시bj움짤 : 스포츠뉴스 : 안구정화 놀이터홍보 놀이터후기공유 피해사례공유

로그인

채팅

글쓰기

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

온카뱅크관리자

2024-06-01 08:00:31

<div id="layerTranslateNotice" style="display:none;"></div>  
        <div class="article_view" data-translation-body="true" data-tiara-layer="article_body" data-tiara-action-name="본문이미지확대_클릭"> 
         <section dmcf-sid="HjWgPrXD5U">
          <figure class="figure_frm origin_fig" dmcf-pid="Xnhd2ATNYp" dmcf-ptype="figure">
           <p class="link_figure"><img alt="게티이미지뱅크 제공" class="thumb_g_article" data-org-src="https://t1.daumcdn.net/news/202406/01/dongascience/20240601080036572dudp.jpg" data-org-width="680" dmcf-mid="Yy8XIuxpG7" dmcf-mtype="image" height="auto" src="https://img4.daumcdn.net/thumb/R658x0.q70/?fname=https://t1.daumcdn.net/news/202406/01/dongascience/20240601080036572dudp.jpg" width="658"></p>
           <figcaption class="txt_caption default_figure">
            게티이미지뱅크 제공
           </figcaption>
          </figure>
          <p dmcf-pid="ZoSifkWAY0" dmcf-ptype="general">여행을 떠나기 전 짐을 싸는 건 여간 귀찮은 일이 아니다. 생각나는 대로 짐을 챙기다 보면 짐이 가방에 다 들어가지 않아 난감할 때도 있다. 그런데 수많은 짐 중 어떤 것부터 골라서 싸야 하는지 알려주는 수학 이론이 있다. 바로 '배낭 문제'다.</p>
          <p dmcf-pid="5gvn4EYcZ3" dmcf-ptype="general"> 배낭 문제란 넣을 수 있는 물건의 총량이 제한된 배낭에 가치의 합이 최대가 되도록 물건을 담는 조합 최적화 문제다. 이때 선택한 물건들의 무게 합은 주어진 최대 무게를 초과하면 안 된다. 배낭 문제는 단순해보이지만, 모든 경우의 수를 직접 확인해봐야 해서 답을 구하기가 어렵다.</p>
          <p dmcf-pid="1aTL8DGkGF" dmcf-ptype="general"> 최대 용량이 10kg인 배낭에 다음과 같은 짐을 담는 상황을 생각해보자. 배낭 문제를 통해 배낭에 담는 물건의 합이 10kg 이하가 되면서 물건 가치의 합은 최대가 되는 경우를 찾을 수 있다. 여기에는 무게순, 가치순, 무게당 가치순으로 배낭을 꾸리는 세 가지 방법이 있다.</p>
          <figure class="figure_frm origin_fig" dmcf-pid="tMrPzLIiYt" dmcf-ptype="figure">
           <p class="link_figure"><img alt="(왼쪽 방법1부터)무게가 무거운 짐부터 배낭을 꾸리면 배낭에는 쌀, 여벌 옷, 음료수, 손전등을 담을 수 있다. 이때 가치의 합은 18점이다, 가치가 높은 것부터 배낭을 꾸리면 배낭에는 구급약, 음료수, 쌀, 손전등까지 담을 수 있다. 이때 가치의 합은 19점이다, 무게당 가치가 높은 것부터 배낭을 꾸리면 배낭에는 쌀을 제외하고 모두 담을 수 있다. 이때 가치의 합은 24점이다. 수학동아 제공" class="thumb_g_article" data-org-src="https://t1.daumcdn.net/news/202406/01/dongascience/20240601080037903joyb.jpg" data-org-width="680" dmcf-mid="Gmn7H4aVYu" dmcf-mtype="image" height="auto" src="https://img4.daumcdn.net/thumb/R658x0.q70/?fname=https://t1.daumcdn.net/news/202406/01/dongascience/20240601080037903joyb.jpg" width="658"></p>
           <figcaption class="txt_caption default_figure">
            (왼쪽 방법1부터)무게가 무거운 짐부터 배낭을 꾸리면 배낭에는 쌀, 여벌 옷, 음료수, 손전등을 담을 수 있다. 이때 가치의 합은 18점이다, 가치가 높은 것부터 배낭을 꾸리면 배낭에는 구급약, 음료수, 쌀, 손전등까지 담을 수 있다. 이때 가치의 합은 19점이다, 무게당 가치가 높은 것부터 배낭을 꾸리면 배낭에는 쌀을 제외하고 모두 담을 수 있다. 이때 가치의 합은 24점이다. 수학동아 제공
           </figcaption>
          </figure>
          <p dmcf-pid="FRmQqoCnY1" dmcf-ptype="general">위의 세 가지 방법 중 '방법 3'으로 배낭을 꾸릴 때 가치의 합이 최대가 된다. 하지만 이 방법 역시 모든 물건을 넣을 수는 없다. 이는 우리가 '0-1 배낭 문제' 를 풀었기 때문이다. 0-1 배낭 문제는 짐을 넣거나 빼거나 둘 중 하나만 선택하는 문제다.</p>
          <p dmcf-pid="3ue0y9nbZ5" dmcf-ptype="general"> 모든 짐을 조금씩 가져가고 싶다면 짐을 쪼개서 가져갈 수 있는 '분할 가능 배낭 문제'를 이용하면 된다. 0-1 배낭 문제는 이를 풀기 위한 가장 효과적인알고리듬이 알려져 있지 않아 여러 조합을 탐색해봐야 하는 반면 분할 가능 배낭 문제는 그리디 알고리즘(여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 근사적으로 최적의 해를 구하는 데 쓰이는 방법)으로 해결할 수 있다.</p>
          <p dmcf-pid="07dpW2LKZZ" dmcf-ptype="general"><strong>※관련기사</strong><br> 수학동아 6월, <strong>설레는 여행지에서 효율적으로 짐 싸기 배낭 문제</strong></p>
          <p dmcf-pid="pzJUYVo9HX" dmcf-ptype="general">[수학동아 편집부 ]</p>
         </section> 
        </div> 
        <p class="" data-translation="true">Copyright © 동아사이언스. 무단전재 및 재배포 금지.</p>

[박진영의 사회심리학] '사회공포증'과 '자기중심적 시각'의 악순환 솔라, 오늘(1일) 서울서 첫 아시아 투어 ‘COLOURS’ 포문 “화려하면서도 감성적…종합선물세트 같아”

댓글 총 0개

업체홍보/구인 더보기

놀이터홍보 더보기

지식/노하우 더보기

판매의뢰 더보기

포토 더보기