[Algorithm] 배낭(Knapsack) 문제 : 동적계획 알고리즘

앞서, 그리디 알고리즘을 통해 해결했던 배낭문제를 동적계획 알고리즘을 이용해서 해결해보자!

---

💡배낭문제의 부분문제를 찾아내기

• 4가지 요소 : 물건, 물건의 무게, 물건의 가치, 배낭의 용량
• 이중에서 물건과 물건의 무게는 부분문제를 정의하는데 고려
  • 이유 : 배낭이 비어있는 상태에서 시작하여 물건을 하나씩 배낭에 담는 것과 안 담는 것을 현재 배낭에 들어있는 물건의 가치의 합에 근거하여 결정해야하기 때문
• 또한 물건을 배낭에 담으려고 할 경우, 배낭 용량의 초과 여부를 검사해야한다.
• 따라서, 부분문제를 아래와 같이 정의!
  • K[i,w] = 물건 1~i 까지 (임시) 배낭의 용량이 w일 때의 최대 가치
    • i= 1~n, w= 1~C
    • n : 물건의 개수, C: 배낭의 용량
    • 여기서 C의 값이 매우 크면, 알고리즘의 수행시간 너무 길어짐
    • 따라서, 다음의 알고리즘은 제한적인 입력에 대해서만 효용성을 가진다.
  • 문제의 최적해 : K[n,C]

 

 

💡Knapsack 의사코드

• 입력 : 배낭의 용량 C, n개의 물건과 각 물건 i의 무게 wi와 가치 vi
• 출력 : K[n,C] (최적해)

• for i = 0 to n K[i,0] = 0	// 배낭의 용량이 0 일때
  for w = 0 to C K[0,w] = 0	// 물건 0 : 어떤 물건도 고려하지 않았을 때
  for i = 1 to n {	// 물건 1에서 n까지 하나씩 고려하여
  	for w = 1 to C {	// w는 배낭의 (임시)용량을 1에서 C까지 각각 증가
      	if(wi > w)	// 물건 i의 무게가 임시 배낭 용량을 초과하면
          	K[i,w] = K[i-1,w]	// 물건 (i-1)까지 고려했을 때의 최대가치가 물건 i까지 고려했을 때의 최대가치로 된다.
          else	// 물건 i를 배낭에 담지 않을 경우와 담을 경우를 고려 (무조건 물건을 바로 넣으면 안된다.)
          	K[i,w] = max{K[i-1,w], K[i-1,w-wi]+vi}	// wi = 물건 i의 무게, vi = 물건 i의 가치
      }
  }
  
  return K[n,C] // 물건을 모두 용량 C까지 고려했을 때

 

➰ 배낭 문제의 부분 문제 간의 함축적인 순서

• 2개의 부분문제 K[i-1, w-wi]와 K[i-1, w]가 미리 계산되어 있어야만 K[i,w]를 계산할 수 있다.

  

 

👩‍💻실행 코드 (C++)

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

vector<vector<int > > arr;
vector<int> C;
vector<int> vi; // 각 물건들의 가치
vector<int> wi; // 각 물건들의 무게

int Max(int a, int b){
    if(a<b){
        return b;
    }
    return a;
}

int main(){
    int n;  // 물건의 수
    int w;  // 각 물건의 가치

    cin >> n >> w;

    for(int i=0;i<n;i++){
        int v;
        int w;
        cin >> v >> w;
        vi.push_back(v);
        wi.push_back(w);
    }

    for(int i=0;i<=w;i++){
        C.push_back(0);
    }

    for(int i=0;i<=n;i++){
        arr.push_back(C);
    }
    
    // 배낭의 용량이 0일 때,
    for(int i=0;i<=n;i++){
        arr[i][0]=0;
    }
    // 어떤 물건도 고려하지 않았을 때,
    for(int i=0;i<=w;i++){
        arr[0][w]=0;
    }

    for(int i=1;i<=n;i++){ // 물건을 1~n까지 고려
        for(int j=1;j<=w;j++){  // 배낭의 임시용량을 1~w까지 고려
            int i_weight = wi[i-1];
            int i_value = vi[i-1];
            if(i_weight>j){  // 초과할 경우,
                arr[i][j] = arr[i-1][j];
            }
            else    // 물건 i를 담지 않았을 때와 담았을 때를 고려
            {
                arr[i][j] = Max(arr[i-1][j], arr[i-1][j-i_weight]+i_value);
            }
        }
    }

    cout << arr[n][w]<<endl;
}

 

⏰ 시간복잡도

• 하나의 부분 문제에 대한 해를 구할 때의 시작복잡도는 무게를 한번 비교한 후, 
  • if 문 : 1개의 부분문제의 해를 참조
  • else 문 : 2개의 해를 참조
  • 총 O(1)의 시간이 걸린다.
• 부분문제의 수는 배열 K의 원소수인 n x C개 이다. (n : 물건의 수, C: 배낭의 용량)
• 따라서, O(1) x n x C = O(nC) 이다.

 

 

➰응용

• 다양한 분야의 의사결정 과정에서 활용
• 원자재의 버리는 부분을 최소화 시키기 위한 자르기/분할
• 금융 포트폴리오와 자산 투자의 선택
• 암호 생성 시스템 등

 

---

Reference

• 서울과학기술대학교 컴퓨터공학과 알고리즘 수업
• 알기쉬운 알고리즘 도서