[c++] 최대점수 구하기(냅색 알고리즘)

최대점수 구하기(냅색 알고리즘)

#include<bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	//freopen("input.txt", "rt", stdin);
	int n, m, s, t;
	cin >> n >> m;
	vector<int> dy(m+1, 0);
	for(int i=0; i<n; i++){
		cin >> s >> t;
		for(int j=m; j>=t; j--){
			dy[j] = max(dy[j], dy[j-t]+s);
		} 
	}
	cout<< dy[m];
	return 0;
}

냅색 알고리즘을 사용해서 주어진 시간내에 최대점수를 구하는 문제이다.

한문제는 한번만 풀수있다는 조건이 있어 이전에 했던 일차원 배열에 값을 저장하는 방법으로는 해결이 되지 않는다.

왜냐하면 0부터 dy배열을 갱신하면 j-t값이 이미 해당문제가 적용되어서 나온 점수값을 참조하기 때문에 

중복해서 풀어버린 것이 된다.

 

예를들어 s가 10이고 t가 5일 때 j가 10이라면 j-t값은 5이므로 dy[5]의 값을 참조하게 된다. 

이러한 경우에 0부터 시작한다면

5의 값은 먼저 갱신되어 있을 것이고 이말은 즉, 5초 걸린 문제를 풀었을 때의 값이 이미 dy[5]에 들어가있다는 말이 된다.

dy[5]에 이미 갱신되어있는 경우 j가 10일 때 dy[5]의 값을 참조하고 그 값에 10점을 더하면 그것은 5초짜리 문제를 두번풀었다는 말이된다.

같은 문제를 두번 풀수 없다는 조건이 있으므로 이런방법으로는 문제의 조건을 충족시킬 수 없다.

 

그러므로 배열의 갱신방향을 m부터 t까지로 바꾸어 푼다면 dy배열을 갱신할 때 j값보다 큰 인덱스를 참조하는 경우는 없으므로 dy[j-t]의 값에는 t초 걸린 문제를 풀었을 때의 값이 들어가 있지 않다.

위의 예시로 다시살펴보면 

s가 10이고 t가 5일 때 j가 10이라면 j-t값은 5이므로 dy[5]의 값을 참조하게 된다.

위의 경우와 다른점은 위에서는 j가 0부터 시작되었으므로 이미 dy[5]의 값은 갱신이 되어 있을 것이다.

그런데 j가 m부터 시작되었다면 dy[5]의 값은 갱신되어있지 않아 있을 것이므로 5초 걸리는 문제를 풀지 않은 상태에서 

s를 더했을 때의 값과 dy[10] 값을 비교할 수 있다. 

즉 5초짜리 문제를 풀지 않은 값에 10점을 더한 값을 구할 수 있다. 

 

원래 냅색 알고리즘은 2차원 배열을 통해 푸는 것이 일반적이지만 이런 방법으로 풀게되면 1차원 배열로도 풀 수 있다.