차례:
정의-배낭 문제는 무엇을 의미합니까?
배낭 문제는 문제와 솔루션을 모두 설명하는 데 사용되는 최적화 문제입니다. 고정 크기 배낭 안에 넣을 수있는 항목 수에 제한이있는 시나리오에서 이름을 파생합니다. 특정한 무게와 값을 가진 일련의 아이템이 주어지면, 배낭의 무게 제한에 따라 배낭에 가능한 많은 가치를 얻는 것이 목표입니다.
배낭 문제를 설명하는 Techopedia
배낭 문제는 일련의 객체 중에서 최적의 객체를 찾는 것에 관한 수학 및 컴퓨터 과학 주제 인 조합 최적화 문제의 예입니다. 이것은 1 세기 이상 동안 연구 된 문제이며, 철저한 검색이 불가능한 최적의 물체 또는 유한 솔루션이 필요한 조합 최적화에서 일반적으로 사용되는 예시적인 문제입니다. 이 문제는 재정적 제약이나 투자 및 포트폴리오 선택과 같은 리소스 할당과 같은 실제 시나리오에서 찾을 수 있습니다. 응용 수학, 복잡성 이론, 암호학, 조합론 및 컴퓨터 과학과 같은 분야에서도 찾을 수 있습니다. 물류에서 가장 중요한 문제입니다.
배낭 문제에서 주어진 항목은 최소한 두 가지 속성, 즉 중요도에 영향을 미치는 항목 값과 제한 측면 인 항목의 무게 또는 부피를 갖습니다. 철저한 검색이 불가능하기 때문에 문제를 더 작은 하위 문제로 나누고 재귀 적으로 실행할 수 있습니다. 이것을 최적의 하위 구조라고합니다. 한 번에 하나의 항목 만 처리하고 배낭에서 현재 무게를 계속 사용할 수 있습니다. 문제 해결사는 여전히 수용 할 수있는 무게를 기준으로 품목을 가져갈 것인지 아닌지를 결정하기 만하면됩니다. 그러나 프로그램 인 경우 재계 산은 독립적이지 않으며 문제를 일으킬 수 있습니다. 동적 프로그래밍 기술을 적용 할 수있는 곳입니다. 각 하위 문제에 대한 솔루션이 저장되므로 계산은 한 번만 수행하면됩니다.
