[알고리즘] knap-sack(냅색, 0-1 배낭문제)
안녕하세요? 코딩충입니다.오늘은 코딩계에서 꽤나 유명한 knap-sack 문제에 대해서 포스팅 하겠습니다. 사람들에 따라서 베낭 문제, 보석가게 도둑 문제 등등 다양한 이름으로 불리웁니다. 문제에 나오는 사람도 도둑, 여행자 등 다양하고 가방, 배낭 등 들고가는 것도 다양하며,가지고 가는 것도 보석, 짐 등 다양하며, 한정된 것도 무게, 크기 등 다양하며, 짐을 나눌 수 있는 문제와 없는 문제 등 다양합니다. 하지만 핵심은 같습니다.자원을 희생시켜서 이득을 얻을 때 최소 자원으로 최대 이득 얻기. 저희는 이 다양한 문제들 중에서 0-1 베낭 문제를 다루겠습니다.가장 간단하고 기본적인 문제입니다.0-1 배낭문제와 다른 변형문제들은 이 포스팅의 메인 주제가 아니니, 위키피디아를 참고해주시길 바랍니다.0-1 ..
코딩/알고리즘
2017. 10. 2. 01:23