베낭문제란?

베낭 문제는 베낭이 존재하고, 베낭에 제한된 비용의 물건을 담을 수 있을 때, 물건들을 조합하여 해당 비용을 가지는 물건이 지닌 가치를 최대로 구하는 조합 최적화 알고리즘입니다.

이러한 베낭 문제는,
문제의 특성에 따라서 크게 두 가지로 나뉩니다.

그리디 알고리즘을 이용하는 분할 가능 베낭 문제.
동적계획 알고리즘(DP)을 이용하는 0-1 베낭 문제.

위 그림과 같이 12kg 베낭에, 원하는 물건을 하나씩 담을 때. 최대 가치를 얻고자 하는 경우에 베낭 알고리즘을 사용합니다.

상단의 경우에는 6kg / 3kg / 2kg / 1kg의 물건을 선택하여 최대 11원의 가치를 얻는 것이 가능합니다.

분할 가능 베낭 문제

그리디 알고리즘을 이용해서 베낭 문제를 푸는 접근법입니다.
탐욕 전략의 원리는, 가장 값이 큰 데이터를 우선해서 담는 것입니다.

물론 위 그림은 기본적으로 0-1 베낭문제이기 때문에 탐욕 접근법을 통한 알고리즘으로 완벽한 답을 구하는 것이 불가능합니다.

분할이 가능하다는 것은, 3kg/4원의 객체를 쪼개서, 1.5kg/2원의 객체로 나누는 것이 가능한 경우를 말합니다.

즉, 위 그림의 경우에는 분할이 불가능하기 때문에 탐욕이 아닌 dp를 이용한 풀이를 구해야 올바른 답을 구할 수 있습니다.

하지만, 여기서는 탐욕법 접근의 원리를 알아보기 위해서 정렬 후의 로직을 체크해보려고 합니다.
1kg 당 원달러를 내림차순으로 정렬하여 탐욕적인 접근이 가능합니다.

무게	원달러
3kg	4원
2kg	2원
1kg	1원
6kg	4원
9kg	5원
4kg	2원
5kg	2원

이후, 정렬된 값을 차례대로 접근하여 12kg을 초과하지 않을 경우에 베낭에 넣도록 하는 것입니다.

이러한 탐욕 접근을 통한, 베낭문제 알고리즘의 기본적인 코드는 아래와 같습니다.

#include <iostream>
#include <vector>
using namespace std;

vector<int> knapsack(int W, vector<int>& w, vector<int>& p) 
{
    int n = w.size() - 1;
    vector<int> K(n + 1, 0);
    int weight = 0;
    for (int i = 1; i <= n; ++i) 
    {
        weight += w[i];
        K[i] = w[i];
        if (weight > W) 
        {
            K[i] -= (weight - W);
            break;
        }
    }
    return K;
}

0-1 베낭 문제

0-1 베낭문제는 DP(다이나믹 프로그래밍)와 백트래킹 두 가지 기법을 통해서 풀 수 있습니다.
이러한 0-1 베낭 문제는 베낭에 담을 수 있는 각 원소를 분해할 수 없을 때, 접근하는 알고리즘입니다.

dp를 통한 풀이

int knapsack(int i, int W, vector<int>& w, vector<int>& p, vector<vector<int>>& memo) 
{
    int value;
    if (i <= 0 || W <= 0) 
    {
        return 0;
    }
    if (memo[i][W] != -1) 
    {
        return memo[i][W];  // 이미 계산한 값이 있다면 바로 반환(dp)
    }
    if (w[i] > W) 
    {
        value = knapsack(i - 1, W, w, p, memo);
    } 
    else 
    {
        int left = knapsack(i - 1, W, w, p, memo);
        int right = knapsack(i - 1, W - w[i], w, p, memo);
        value = max(left, p[i] + right);
    }
    memo[i][W] = value; // 계산한 값 저장
    return value;
}

먼저, w 배열과 p 배열은 각각 무게와 값을 담은 배열입니다.
위 그림에서는 각각 원소의 kg과 원달러에 해당하는 값을 나누어 담은 것이죠.

memo배열은 이중 벡터로서, dp 역할을 해줍니다. memo 벡터의 행은 n+1값. 즉, w/p 배열 크기+1로 사이즈를 설정해주고, 열은 W. 즉, 목표 리미트값(그림에서는 12kg)을 설정하여, 각 메모이제이션에 저장된 [i][W] 각, 행의 목푯값에 저장된 데이터 유무를 체크하고 값이 있을 경우 재활용 하도록 해줍니다.

만약 값이 없을 경우에만,
재귀함수를 이용해서 w/p 배열의 범위-1에서부터 차례차례 감산해가며(최대무게에서 현재 인덱스에 해당하는 무게를 제외) 깊게 파고듭니다.

그렇게 최종적으로, 값을 구합니다.

백트래킹을 이용한 풀이

int max_value = 0;

void knapsack_backtracking(int i, int W, vector<int>& w, vector<int>& p, int current_value) 
{

    if (i == 0 || W <= 0) 
    {
        max_value = max(max_value, current_value);
        return;
    }
    if (w[i] > W) 
    {
        knapsack_backtracking(i - 1, W, w, p, current_value); // 해당 물건을 선택하지 않는 경우
    } 
    else 
    {
        knapsack_backtracking(i - 1, W, w, p, current_value); // 해당 물건을 선택하지 않는 경우
        knapsack_backtracking(i - 1, W - w[i], w, p, current_value + p[i]); // 해당 물건을 선택하는 경우
    }
}

백트래킹을 이용한 풀이는 dp를 이용한 풀이보다 다소 쉽습니다.

max_value는 현재 결과값과 기존 결과값을 비교하여, 리턴하고,
현재 인덱스 값의 무게가 W를 초과하지 않는 경우에만,
물건을 선택한 경우와 선택하지 않은 경우로 분기하여 재귀호출하여 깊게 파고듭니다.