안녕하세요! 소리입니다 👋
이번 글에서는 유명한 PS 문제인 배낭 문제에 대한 내용을 준비했어요.
배낭 문제가 무엇인지부터 여러 배낭 문제의 변형을 다뤄볼게요!

---

🎒 배낭 문제란?

배낭 문제는 한정된 무게만 담을 수 있는 배낭에 여러 물건을 넣을 때, 어떤 조합의 물건을 넣는 것이 가장 높은 가치를 만드는지 찾는 문제를 말해요.

배낭 문제는 물건의 특징에 따라 여러 형태로 나눌 수 있어요.

• 분할 가능 배낭 문제
• 0-1 배낭 문제
• 무한 배낭 문제

🪣 분할 가능 배낭 문제

분할 가능 문제는 물건을 나눌 수 있는 문제를 말해요.

만약 양동이에 모래나 흙을 담아야 하는 경우, 주어진 모래나 흙을 모두 담지 않고 일부만 담을 수 있어요.
이처럼 주어진 물건들을 나눌 수 있는 경우를 분할 가능 배낭 문제라고 해요.

해결 방법

분할 가능 배낭 문제에서는 단위 무게당 가장 가치가 높은 물건을 담는 것이 유리해요.

그림을 통해 자세히 설명할게요.
그림에서는 1L당 각각 $10, $8, $7, $4, $2의 가치를 가지는 액체가 2L, 4L, 3L, 2L, 4L 주어지고, 10L를 담을 수 있는 양동이가 주어졌어요.
이때, 어떻게 담는 것이 양동이의 가치를 가장 높게 만들 수 있을까요?

먼저 양동이에 단위무게당 가치가 높은 순으로 담아요.
그러다 양동이가 가득 차서 어떤 액체를 모두 담지 못하는 경우에는 양동이가 가득 찰 때까지만 담아요.
이를 통해 양동이를 최대의 가치로 채울 수 있게 돼요.

이 방법을 사용하면 양동이를 채우고 남은 액체는 모두 양동이에 담긴 액체보다 가치가 높지 않게 돼요.
따라서 양동이에 담긴 조합이 가장 높은 가치를 가지는 조합이 돼요.

🤔 탐욕 기법이란?

탐욕 기법(그리디, Greedy)은 매 단계마다 현재 시점의 최적 방법을 선택하는 것을 말해요.
어떤 문제의 부분 최적 방법이 전체 최적 방법으로 이어진다면, 탐욕 기법을 사용하는 것이 효율을 높여요.

분할 가능 배낭 문제는 탐욕 기법을 적용하는 것이 효율적이에요.

📦 0-1 배낭 문제

0-1 배낭 문제는 분할 가능 배낭 문제와 달리 물건을 쪼갤 수 없어요.
따라서 일부분만 담지 못하고 물건을 가방에 담거나, 담지 않는 선택만 할 수 있어요.

⚠️ 0-1 배낭 문제를 탐욕 기법으로 해결할 수 없는 이유

0-1 배낭 문제는 분할 가능 배낭 문제처럼 탐욕 기법을 사용할 수 없어요.
분할 가능 배낭 문제와 달리 물건을 쪼갤 수 없기 때문에, 단위무게당 가치가 높더라도 무게를 너무 많이 차지해 공간을 효율적으로 사용할 수 없는 경우가 있기 때문이에요.

그림에서 왼쪽은 1kg당 $12의 가치를 가지는 물건을 넣었어요.
이때, 남은 무게가 2kg밖에 남지 않아서 다른 물건을 넣을 수 없어요.

그러나 오른쪽은 가치가 조금 낮은 1kg당 $10의 가치를 가지는 물건이지만 두 개를 넣을 수 있어서 공간을 더욱 효율적으로 사용할 수 있게 돼요.
이 때문에 왼쪽은 총 $48의 가치를 가지는 것에 비해, 오른쪽은 $60의 가치를 가지게 돼요.

따라서 0-1 배낭 문제는 탐욕 기법으로 문제 해결이 불가능해요.

모든 경우 확인해서 해결하기

가장 간단한 방법은 모든 경우를 확인하는 방법이에요.
주어진 물건 집합의 모든 부분집합을 일일이 확인하면서 배낭 무게를 초과하지 않는 조합 중 가장 가치가 큰 것을 찾는 방법을 사용하면 0-1 배낭 문제를 해결할 수 있어요.

그러나 이 방법은 매우 비효율적이에요.
물건이 조금만 많아져도 확인해야 하는 집합의 개수가 지수적으로 커지기 때문이에요.

원소가 $N$개 있는 집합의 부분집합의 개수는 $2^N$이에요.
따라서 부분집합을 모두 확인하는 방법은 $O(2^N)$의 시간 복잡도를 가져요.

이 때문에 물건의 개수가 매우 적으면 모든 경우를 확인하는 방법을 사용할 수 있지만, 일반적으로 사용하기는 힘들어요.

구현

구현은 재귀를 이용해 구현했어요.

Python

# items: list[(weight: int, value: int)]
def knapsack(max_weight, total_weight, total_value, items):
    if len(items) == 0:
        return total_value if total_weight <= max_weight else 0
    else:
        # 물건 미포함
        p = knapsack(max_weight, total_weight, total_value, items[1:])

        # 물건 포함
        q = knapsack(max_weight, total_weight + items[0][0], total_value + items[0][1], items[1:])

        return max(p, q)

Rust

struct Item {
    weight: u32,
    value: u32,
}

fn knapsack(max_weight: u32, total_weight: u32, total_value: u32, items: &[Item]) -> u32 {
    if items.is_empty() {
    	// 부분집합의 무게 합이 배낭 무게를 초과하면 0 반환
        if total_weight <= max_weight { total_value } else { 0 }
    }
    else {
    	// 물건 미포함
        let p = knapsack(max_weight, total_weight, total_value, &items[1..]);

		// 물건 포함
        let q = knapsack(max_weight, total_weight + items[0].weight, total_value + items[0].value, &items[1..]);
        
        p.max(q)
    }
}

부분 문제로 분할해서 해결하기

핵심 아이디어

0-1 배낭 문제에서는 각 물건들에 대해 배낭에 넣을 것인지, 넣지 않을 것인지의 두 가지 선택을 해요.

어떤 물건 A를 배낭에 넣는 경우의 최대 가치는 어떻게 될까요?
물건 A의 가치에 물건 A의 무게를 뺀 나머지 무게의 배낭의 최대 가치를 더한 것과 같아요.
이를 수식으로 표현하면 다음과 같아요.

$K_w(U)=a_v+K_{w-a_w}(U-\{a\})$

U : 모든 물건 집합

반대로 물건 A를 넣지 않는 경우의 최대 가치는 어떻게 될까요?
이 경우는 다른 물건들로 만든 배낭의 최대 가치와 같아요.

$K_w(U)=K_w(U-\{a\})$

따라서 물건 A를 고려한 배낭의 최대 가치는 다음과 같이 정리할 수 있어요.

$K_w(U)=max\{a_v+K_{w-a_w}(U-\{a\}),\,K_w(U-\{a\})\}$

이제 수식을 조금 더 확장해 볼게요.
$K_w(U-\{a\})$는 어떻게 구할 수 있을까요?

모든 물건 집합에는 물건 A 말고도 물건 B가 있을 거예요.
따라서 수식을 다음처럼 변경할 수 있어요.

$K_w(U-\{a\})=max\{b_v+K_{w-b_w}(U-\{a, b\}),\,K_w(U-\{a, b\})\}$

지금까지의 수식을 통해 $K_w(U)$을 계산하기 위해서 $K_w(U-\{a\})$이 필요하고, $K_w(U-\{a\})$을 계산하기 위해 $K_w(U-\{a, b\})$이 필요하다는 것을 알 수 있어요.

이를 반대로 생각하면 배낭 문제를 물건 하나씩 고려하며 계산하면 모든 물건을 고려한 배낭의 최대 가치를 구할 수 있다는 것으로 바꿀 수 있어요.

🤔 동적 계획법이란?

동적 계획법(다이나믹 프로그래밍, DP)은 큰 문제를 작은 부분 문제로 나누고, 각 부분 문제의 해를 저장하여 재활용하는 방법을 말해요.
큰 문제의 답을 작은 문제의 답을 모아서 계산할 수 있는 최적 부분 구조 형태의 문제 중, 작은 문제가 반복되면 동적 계획법으로 문제를 해결하는 것이 효율적이에요.

0-1 배낭 문제는 위의 조건을 만족하므로, 동적 계획법을 적용해 효율적으로 해결할 수 있어요.

계산 과정

맨 처음의 그림이에요.
이 예시에서 가능한 가방의 최대 가치를 구해볼게요.

구하는 과정을 시각화하기 위해 제시된 문제를 표로 바꿔보았어요.

먼저 상자를 고려해볼게요.
상자는 무게가 $6kg$이므로, $6kg$ 미만의 무게에서는 상자를 넣을 수 없어요.
하지만 $6kg$ 이상에서는 넣을 수 있고, 넣는 것이 더 높은 가치를 만들어요.

빨간색은 넣지 않는 경우를, 파란색은 물건을 넣는 것이 더 높은 가치를 만드는 경우를 표현했어요.

다음은 책을 고려했어요.
책은 $4kg$ 이상에서 넣을 수 있지만, $6kg$ 이상에서는 넣는 것이 오히려 더 낮은 가치를 만들어요.

이어서 인형과 펜을 차례대로 고려했어요.

이 표에서 마지막 줄은 모든 물건을 고려한 최대 가치가 저장된 줄이에요.
따라서 $7kg$ 배낭의 최대 가치는 $$14$라는 것을 알 수 있어요.

구현

구현은 상향식(Bottom-Up) 방법을 사용했어요.
테이블의 이름은 dp를 사용했어요.

Python

# items: list[(weight: int, value: int)]
def knapsack(max_weight, items):
    dp = [[0] * (max_weight + 1) for _ in range(len(items) + 1)]

	# 각 물건을 차례대로 고려하기 위해 순차적으로 접근
    for k in range(len(items)):
    
    	# 0부터 max_weight까지의 각 칸을 채우기 위해 반복
        for i in range(1, max_weight + 1):
            if items[k][0] <= i:
            	# k번 물건을 넣는 경우 = k번 물건 가치 + (i - k번 물건 무게) 무게의 기존 최대 가치
                # k번 물건을 넣지 않은 경우 = i 무게의 기존 최대 가치
                # k번 물건을 고려한 경우의 최대 가치 = 두 경우의 최댓값
                dp[k + 1][i] = max(dp[k][i - items[k][0]] + items[k][1], dp[k][i])
            else:
            	# 물건을 넣을 수 없으면 기존의 최대 가치가 최댓값이 됨
                dp[k + 1][i] = dp[k][i]
    
    # 모든 물건을 고려한 줄에서 최대 가치 반환
    return dp[len(items)][max_weight]

Rust

struct Item {
    weight: u32,
    value: u32,
}

fn knapsack(max_weight: u32, items: &[Item]) -> u32 {
    let mut dp = vec![vec![0; max_weight as usize + 1]; items.len() + 1];

	// 각 물건을 차례대로 고려하기 위해 순차적으로 접근
    for k in 0..items.len() {
    	
        // 0부터 max_weight까지의 각 칸을 채우기 위해 반복
        for i in 1..=max_weight as usize {
            if items[k].weight as usize <= i {
            	// k번 물건을 넣는 경우 = k번 물건 가치 + (i - k번 물건 무게) 무게의 기존 최대 가치
                // k번 물건을 넣지 않은 경우 = i 무게의 기존 최대 가치
                // k번 물건을 고려한 경우의 최대 가치 = 두 경우의 최댓값
                dp[k + 1][i] = dp[k][i].max(dp[k][i - items[k].weight as usize] + items[k].value);
            }
            else {
            	// 물건을 넣을 수 없으면 기존의 최대 가치가 최댓값이 됨
                dp[k + 1][i] = dp[k][i];
            }
        }
    }

	// 모든 물건을 고려한 줄에서 최대 가치 반환
    dp[items.len()][max_weight as usize]
}

최적화

위의 코드는 2차원 배열을 이용했어요.
그러나 연산 순서를 수정하면 1차원 배열로 배낭 문제를 해결할 수 있도록 최적화할 수 있어요.

표에서 어떤 한 줄을 계산하기 위해 필요한 값은 바로 윗줄의 값이에요.
또한 어떤 칸을 계산할 때 필요한 값은 해당 칸보다 작은 무게의 칸이에요.

따라서 다음처럼 배열을 관리할 수 있어요.

큰 무게의 칸을 우선적으로 갱신하면 1차원 배열로도 배낭 문제를 해결할 수 있게 구성할 수 있어요.

Python

# items: list[(weight: int, value: int)]
def knapsack(max_weight, items):
    dp = [0] * (max_weight + 1)

    # 각 물건을 차례대로 고려하기 위해 순차적으로 접근
    for k in range(len(items)):

        # 1차원 배열을 사용하기 위해 무게가 큰 순으로 순회
        w = items[k][0]
        for i in range(max_weight, w - 1, -1):
            dp[i] = max(dp[i - w] + items[k][1], dp[i])

    # 모든 물건을 고려한 줄에서 최대 가치 반환
    return dp[max_weight]

Rust

struct Item {
    weight: u32,
    value: u32,
}

fn knapsack(max_weight: u32, items: &[Item]) -> u32 {
    let mut dp = vec![0; max_weight as usize + 1];

    // 각 물건을 차례대로 고려하기 위해 순차적으로 접근
    for k in 0..items.len() {

        // 1차원 배열을 사용하기 위해 무게가 큰 순부터 순회
        let w = items[k].weight as usize;
        for i in (w..=max_weight as usize).rev() {
            dp[i] = dp[i].max(dp[i - w] + items[k].value);
        }
    }

    // 모든 물건을 고려한 줄에서 최대 가치 반환
    dp[max_weight as usize]
}

⛲️ 무한 배낭 문제

무한 배낭 문제는 0-1 배낭 문제의 변형 문제예요.
다른 규칙은 모두 비슷하지만, 같은 물건을 무제한으로 담을 수 있다는 차이점이 있어요.

무한 배낭 문제로 풀 수 있는 대표적인 예시는 동전 교환 문제예요.
동전 교환 문제는 주어진 금액을 얼마나 적은 개수의 동전으로 교환할 수 있는지 찾는 문제를 말해요.
이때 같은 종류의 동전을 개수 제한 없이 사용할 수 있는 것이 특징이에요.

🤔 동전 교환 문제를 무한 배낭 문제로 해결할 수 있는 이유는?

동전 교환 문제는 무한 배낭 문제를 변형한 형태의 문제로 해석할 수 있어요.

동전의 개수를 물건의 가치로 생각하고, 동전의 가치를 물건의 무게로 생각하면 동전 교환 문제를 배낭 문제와 같은 DP 구조를 가지는 문제로 해결할 수 있어요.
이때, 동전 교환 문제는 가치 감소를 최소화하는 형태의 배낭 문제가 돼요.

해결 방법

무한 배낭 문제는 0-1 배낭 문제와 달리 물건을 계속하여 사용할 수 있어요.
따라서 물건을 여러 번 고려할 수 있도록 구성해야 해요.

이는 물건 A에 대한 수식의 더 작은 배낭 무게를 이미 물건 A를 고려한 경우의 값으로 가져오는 것으로 계산할 수 있어요.

구현

0-1 배낭 문제의 업데이트 방향을 반대로 하면 무한 배낭 문제를 해결할 수 있어요.

Python

# items: list[(weight: int, value: int)]
def knapsack(max_weight, items):
    dp = [0] * (max_weight + 1)

    # 각 물건을 차례대로 고려하기 위해 순차적으로 접근
    for k in range(len(items)):

        # 물건을 계속해서 고려하기 위해 무게가 작은 순부터 순회
        w = items[k][0]
        for i in range(w, max_weight + 1):
            dp[i] = max(dp[i - w] + items[k][1], dp[i])

    # 최대 가치 반환
    return dp[max_weight]

Rust

struct Item {
    weight: u32,
    value: u32,
}

fn knapsack(max_weight: u32, items: &[Item]) -> u32 {
    let mut dp = vec![0; max_weight as usize + 1];

    // 각 물건을 차례대로 고려하기 위해 순차적으로 접근
    for k in 0..items.len() {

        // 물건을 계속해서 고려하기 위해 무게가 작은 순부터 순회
        let w = items[k].weight as usize;
        for i in w..=max_weight as usize {
            dp[i] = dp[i].max(dp[i - w] + items[k].value);
        }
    }

    // 최대 가치 반환
    dp[max_weight as usize]
}

---

배낭 문제는 한정된 자원 중 최선의 경우를 선택하는 상황에 적용할 수 있는 여러 원리를 포함하고 있어요.
따라서 배낭 문제를 이해하고, 여러 응용 문제를 해결할 수 있게 된다면 다른 알고리즘 문제를 해결하는 능력을 키울 수 있을 거예요.

다음에도 유익한 내용으로 찾아올게요! 😁