백준 12865 평범한 배낭 c++

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

int dp[100001];

int main(void)
{
	int n,k;
	cin >> n >> k;
	vector<pair<int,int> > v;
	for(int i=0; i<n; i++) {
		int a,b;
		cin >> a >> b;
		v.push_back({a,b});
	}
	 
	for(int i=0; i<n; i++) {
		int rem[100001] = {0,};
		for(int j=0; j<=k; j++) {
			rem[j] = dp[j];
		}
		for(int j=0; j<100001; j++) {
			if(j + v[i].first <= k) {
				dp[j+v[i].first] = max(rem[j] + v[i].second,dp[j+v[i].first]);	
			}
			else if(j + v[i].first > k)	break;
		}
	} 
	
	int max_value = -1;
	
	for(int i=0; i<=k; i++) {
		max_value = max(max_value,dp[i]);
	}
	
	cout << max_value;
	
	return 0;
}

 

알고리즘 분류를 보고 knapsnack 알고리즘이란걸 알게 되어 knapsnack 알고리즘에 대해 알아보았습니다.

 

knapsnack 알고르즘에 대해서 간단히 설명하자면

 

이전에 들어있는 배낭 물건들의 합과 현재 넣을 물건의 합이 배낭이 버틸수있는 무게보다 낮으면서 가치가 높을때 dp값을 수정해주는 것입니다.

 

예를 들어 물건이 3개 있고 배낭이 버틸수 있는 무게가 6이라고 가정하겠습니다.

 

물건은 차례로

3 / 14
2 / 8
3 / 9

무게/가치 의 값을 가집니다.

개수/ 무게	1	2	3	4	5	6
1	0	0	14	14	14	14
2	0	8	14	14	22	22
3	9	8	14	14	22	23

위의 코드를 이용해 출력해보면 위와같은 값이 나옵니다.

 

특이점이 있다면 rem 배열을 이용해 이전 dp값을 저장해준것인데 그렇지 않으면

맨처음 3 /14 를 저장할때 dp[6]의 값이 dp[3] + 14가 되어 28로 저장됩니다.

 

**참고

https://gsmesie692.tistory.com/113

Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)