[알고리즘/C,C++] 평범한 배낭(Knapsack Problem)

문제

물건의 갯수 : n
가방이 견딜 수 있는 무게 : k
n 개의 물건의 무게와 가치 : (wi, vi)

배낭에 넣을 수 있는 물건들의 가치합의 최대값을 출력한다.

완전탐색을 사용하는 경우

완전탐색으로 평범한 배낭 문제를 풀게 되면 물건의 개수=n 일때 시간복잡도 O(2^n)만큼의 시간이 걸린다.

다이나믹 프로그래밍을 사용하는 경우

다이나믹 프로그래밍을 이용하면, 이차원 테이블을 순회하는 만큼인 시간복잡도 O(n^2)으로 문제를 풀 수 있다.

풀이 과정

왼쪽의 테이블은 각 물건들의 무게(w)와 가치(v)
오른쪽 테이블 value[i][k] 은 견딜 수 있는 무게(k)에 따른 i번째 물건까지 고려한 총 가치의 합이다.

i가 0일때와 k가 0 일때 테이블을 모두 0으로 초기화

다음 점화식을 이용하여 나머지 테이블을 완성한다.

소스코드

#include <iostream>
using namespace std;

struct Thing{
    int weight, val;
};

int value[101][100001], n, k;
Thing thing[101];

int main(){
    cin >> n >> k;
  
  	//물건들의 무게와 가치(w, v)를 입력받는다.
    for(int i = 1 ; i<=n ; i++){
        int w, v;
        cin >> w >> v;
        thing[i] = {w, v};
    }
  
  	//다이나믹 프로그래밍
    for(int i = 1 ; i<=n ; i++){
        for(int j = 1 ; j<=k ; j++){
            int wi = thing[i].weight;
            int vi = thing[i].val;
  
            //i 번째 물체의 무게를 포함할 수 없는 경우
            if(wi > j){
                value[i][j] = value[i-1][j];
            }//i 번째 물체의 무게를 배낭의 용량(k)가 포함할 수 있는 경우
  			else{
                value[i][j] = max(value[i-1][j], vi+value[i-1][j-wi]);
            }
            
        }
    }
    cout << value[n][k];
    return 0;
}