냅색(Knapsack) 알고리즘

무게 제한이 걸려있는 가방에 가치를 최대로 하게끔 물건을 넣는 방법을 알아보자!

 

대표 문제: 12865 평범한 배낭

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

가치를 최대로 하는 문제이니, dp에 가치를 저장해서 해결한다.

 

Value(i,w)란 i번째 물건까지, w무게만큼 골랐을 때 최대가치를 말한다고 가정한다.

(단, i는 물건의 index, w는 현재 가방에 담겨있는 무게)

 

Value(i,w)는 2가지 경우로 나눠서 생각할 수 있다.

  (1) i-1개의 물건까지 고른 경우

  (2) i-1개의 물건까지 고르고 새로 i번의 물건을 선택한 경우

 

 위 두 가지 경우에서 최대가 되는 경우를 선택하면 된다.

 

 

Value(i, w) =  max(Value(i - 1, w), Value(i - 1, w - w[i]) + v[i])

Value(i, w) =  Value(i-1,w)       //(w<w[i])

 

  (1) i-1개의 물건까지 고른 경우는 빨간색이다.

  (2) i-1개의 물건까지 고르고 새로 i번의 물건을 선택한 경우는 파란색이다. (w>=w[i] 만 가능)

    - 새로운 i번째 value를 더해준다

    - i번째 무게만큼 늘어나므로, 그 전 단계에서 w[i]를 뺀 경우를 사용

 

 

Bottom-up 방식과 Top-down 방식 중 편한 방법을 사용한다.

 

Bottom-up

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);


	cin >> N >> K;
	for (int i = 1;i <= N;i++) 
		cin >> W[i] >> V[i];



	for (int i = 1;i <= N;i++) {
		for (int j = 1;j <= K;j++) {
			if (j >= W[i])
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
			else
				dp[i][j] = dp[i - 1][j];
		}
	}

	cout << dp[N][K];
	return 0;
}

 

 

 

Top-down

int knapsack(int idx, int weight) {

	if (idx < 0)
		return 0;


	if (dp[idx][weight] != 0)
		return dp[idx][weight];


	if (W[idx] > weight) 
		return knapsack(idx - 1, weight);

	return dp[idx][weight] = max(knapsack(idx - 1, weight), knapsack(idx - 1, weight - W[idx])] + V[idx]);
}