배낭 문제

0-1 배낭 문제는 조합 최적화 문제 중 가장 기본적이고 대표적인 형태이다. 이 문제에서는 각 물건을 배낭에 넣거나 넣지 않는 두 가지 선택만 가능하며, 물건을 쪼개어 일부만 넣을 수 없다. 따라서 각 물건에 대한 선택은 0(선택 안 함) 또는 1(선택함)의 값을 가지게 되어 '0-1'이라는 이름이 붙었다.

이 문제의 목표는 배낭의 최대 용량을 초과하지 않으면서, 선택한 물건들의 총 가치를 최대화하는 것이다. 이는 제한된 자원 내에서 최적의 가치를 얻어야 하는 다양한 실제 문제를 모델링하는 데 유용하다. 예를 들어, 제한된 예산으로 가장 가치 있는 투자 상품을 선택하는 투자 포트폴리오 최적화나, 제한된 화물 공간에 가장 수익성이 높은 상품을 싣는 문제 등에 적용될 수 있다.

0-1 배낭 문제를 해결하는 대표적인 방법으로는 동적 계획법이 있다. 이 방법은 배낭의 용량과 고려하는 물건의 개수를 점진적으로 늘려가며 각 부분 문제의 최적해를 테이블에 저장하고, 이를 이용해 전체 문제의 최적해를 구한다. 다른 접근법으로는 탐욕 알고리즘이나 분기 한정법이 있지만, 탐욕 알고리즘은 최적해를 보장하지 않으며, 분기 한정법은 정확한 해를 구할 수 있지만 계산 시간이 많이 소요될 수 있다.

이 문제는 NP-난해 문제에 속하며, 물건의 수가 많아질수록 가능한 조합의 수가 기하급수적으로 증가한다. 이러한 계산적 복잡성 때문에, 대규모 문제를 해결하기 위해서는 정확한 해법 대신 근사 알고리즘이나 휴리스틱 방법이 사용되기도 한다.

분할 가능 배낭 문제는 배낭 문제의 주요 변형 중 하나로, 각 물건을 쪼개어 일부만 담는 것이 허용된다는 점이 특징이다. 예를 들어 설탕이나 곡물처럼 연속적인 물건을 나누어 담을 수 있는 상황을 모델링한다. 이 문제에서는 각 물건의 단위 무게당 가치(가치/무게 비율)를 계산하여, 그 비율이 높은 물건부터 우선적으로 배낭에 담는 탐욕 알고리즘으로 최적해를 구할 수 있다. 이는 0-1 배낭 문제가 NP-난해인 것과 대조적으로, 분할 가능한 경우에는 다항 시간 내에 해결이 가능하다는 점에서 중요하다.

해결 방법은 직관적이다. 먼저 모든 물건에 대해 단위 무게당 가치를 구하고, 이 값을 기준으로 내림차순으로 정렬한다. 그런 다음 정렬된 순서대로 물건을 배낭에 담되, 배낭의 남은 용량보다 물건의 무게가 크다면 해당 물건의 일부만 쪼개어 남은 용량을 꽉 채운다. 이 탐욕 알고리즘 접근법은 항상 최대 가치를 보장하는 최적해를 제공한다.

이 문제는 자원을 나누어 할당해야 하는 실제 자원 할당 문제에 널리 적용된다. 예를 들어, 제한된 예산으로 서로 다른 수익률을 가진 여러 프로젝트에 투자할 때, 각 프로젝트에 투자 금액을 연속적으로 분배할 수 있다면 이는 전형적인 분할 가능 배낭 문제가 된다. 또한 커팅 스톡 문제의 일부 변형이나, 연속적인 원자재를 최적으로 절단하는 문제에서도 유사한 모델이 사용된다.

다중 배낭 문제는 배낭이 하나가 아닌 여러 개가 주어지는 조합 최적화 문제이다. 각 배낭은 서로 다른 용량을 가질 수 있으며, 목표는 각 배낭의 용량을 초과하지 않으면서 모든 배낭에 할당된 물건들의 총 가치를 최대화하는 것이다. 이 문제는 자원 할당이나 물류에서 여러 대의 차량이나 창고에 물건을 효율적으로 나누어 싣는 상황을 모델링할 때 유용하게 적용된다.

다중 배낭 문제는 단일 배낭 문제보다 훨씬 복잡한 문제로, NP-난해 문제에 속한다. 문제를 해결하기 위해 동적 계획법, 분기 한정법, 메타휴리스틱 알고리즘 등 다양한 기법이 사용된다. 특히 배낭의 수가 많아질수록 가능한 해의 조합이 기하급수적으로 증가하기 때문에, 최적해를 찾는 것은 매우 어려워진다.

이 문제의 변형으로는 각 물건이 특정 배낭에만 할당될 수 있는 제약이 추가되거나, 배낭을 사용하는 데 드는 비용이 고려되는 경우 등이 있다. 이러한 변형들은 실제 산업 현장의 복잡한 제약 조건을 반영하기 위해 연구되고 있다.

동적 계획법은 배낭 문제를 해결하는 데 널리 사용되는 효율적인 방법 중 하나이다. 이 방법은 문제를 더 작은 하위 문제로 나누어 해결하고, 그 결과를 저장해 재사용함으로써 중복 계산을 피하고 최적해를 찾는다. 특히 0-1 배낭 문제와 같이 각 물건을 선택하거나 선택하지 않는 이진 결정을 요구하는 문제에 효과적이다.

동적 계획법을 배낭 문제에 적용할 때는 일반적으로 2차원 배열을 사용한다. 이 배열의 행은 고려할 물건의 순서를, 열은 배낭의 현재 용량을 나타낸다. 각 셀에는 특정 물건까지 고려하고 특정 용량에서 얻을 수 있는 최대 가치를 저장한다. 점화식을 통해 이전 단계의 결과를 바탕으로 현재 단계의 최적값을 계산해 나간다.

이 접근법의 시간 복잡도는 물건의 수(n)와 배낭의 최대 용량(W)에 비례하여 O(nW)이다. 이는 모든 가능한 하위 문제를 한 번씩만 계산하기 때문에, 무차별 대입법보다 훨씬 효율적이다. 그러나 용량 W가 매우 큰 경우에는 계산 비용이 커질 수 있다.

동적 계획법은 조합 최적화 문제를 해결하는 핵심 기법으로, 배낭 문제 외에도 최단 경로 문제나 자원 할당 문제 등 다양한 분야에 응용된다. 이 방법을 통해 얻은 해는 항상 전역 최적해임이 보장된다는 장점이 있다.

탐욕 알고리즘은 배낭 문제를 해결하는 직관적이고 빠른 방법 중 하나이다. 이 방법은 각 단계에서 가장 좋아 보이는 선택을 하는 방식으로, 즉 무게 대비 가치가 가장 높은 물건부터 우선적으로 배낭에 넣는 접근법을 사용한다. 특히 분할 가능 배낭 문제에서는 이 방법이 최적해를 보장한다. 분할 가능한 경우, 물건의 일부를 쪼개어 넣을 수 있기 때문에 단위 무게당 가치(가치/무게 비율) 순으로 정렬한 뒤, 높은 순서대로 배낭이 가득 찰 때까지 채우면 된다.

그러나 0-1 배낭 문제와 같이 물건을 통째로 넣거나 넣지 않아야 하는 경우에는 탐욕 알고리즘이 항상 최적해를 찾는다는 보장이 없다. 예를 들어, 가장 가치가 높은 단일 물건이 배낭 대부분의 용량을 차지해 다른 여러 개의 가치 있는 물건들을 넣지 못하게 하는 경우, 전체적인 가치 합은 최적이 아닐 수 있다. 따라서 0-1 배낭 문제를 해결할 때 탐욕 알고리즘은 근사 해법으로 사용되며, 그 성능은 문제 인스턴스에 따라 달라진다.

탐욕 알고리즘의 주요 장점은 간단하고 실행 속도가 매우 빠르다는 점이다. 동적 계획법에 비해 필요한 계산량과 메모리가 적어, 제한 시간 내에 합리적인 해를 빠르게 구해야 하는 실시간 응용 분야나 자원 할당 문제의 초기 해를 구하는 데 유용하게 쓰인다. 하지만 최적성을 보장하지 못하는 한계가 있으므로, 문제의 종류와 요구되는 해의 정확도에 따라 다른 알고리즘과 비교하여 선택해야 한다.

분기 한정법은 조합 최적화 문제, 특히 NP-난해 문제로 분류되는 0-1 배낭 문제를 해결하는 데 사용되는 정확한 알고리즘 기법이다. 이 방법은 가능한 모든 해의 조합을 체계적으로 탐색하되, 탐색 공간을 효과적으로 줄여서 최적해를 찾는 데 걸리는 시간을 단축한다. 기본 아이디어는 문제를 부분 문제로 나누고(분기), 각 부분 문제에 대해 해의 상한값을 계산하여 현재까지 찾은 최선의 해보다 나을 수 없는 부분 문제는 더 이상 탐색하지 않는(한정) 것이다.

분기 한정법의 핵심은 한정 작업이다. 각 노드(부분 문제)에서 배낭에 넣을 수 있는 남은 물건들을 고려했을 때 얻을 수 있는 이론상 최대 가치의 상한을 추정한다. 일반적으로 분할 가능 배낭 문제의 해법을 이용해 상한을 빠르게 계산한다. 이 상한값이 현재까지 발견된 최적해의 실제 가치보다 낮거나 같다면, 해당 노드와 그 하위 노드들은 더 이상 탐색할 가치가 없다고 판단하고 가지치기를 수행한다. 이를 통해 불필요한 탐색을 방지하고 실행 시간을 크게 줄일 수 있다.

이 방법은 동적 계획법이 큰 용량에서 비효율적일 수 있는 경우나, 탐욕 알고리즘으로는 최적해를 보장할 수 없는 경우에 유용하다. 분기 한정법은 최적해를 보장하면서도, 문제의 특성에 따라 효율적으로 동작할 수 있다. 구현 방식에 따라 너비 우선 탐색, 최선 우선 탐색, 깊이 우선 탐색 등 다양한 탐색 전략과 결합되어 사용된다.

분기 한정법은 배낭 문제 외에도 외판원 문제, 작업 스케줄링, 정수 계획법 등 다양한 조합 최적화 문제를 해결하는 데 폭넓게 응용된다. 이 기법은 문제의 구조를 활용한 효율적인 상한 계산 함수 설계가 전체 성능을 결정하는 중요한 요소가 된다.