배낭문제에서 넣은 것을 저장하는 아이디어

 

문제는 https://www.acmicpc.net/problem/14728 문제를 예로 들었다.

 

배낭문제를 푸는데 어떤 것을 넣었는지 기억해야하는 문제가 있었다. 나의 경우 trace 벡터를 만들고 배낭에 넣을 때의 따라 벡터를 조절하며 문제를 해결했다. 그러나 2차원 크기의 벡터가 필요하기 때문에 메모리가 상당히 많이 필요할 것으로 보여서 N이 충분히 작을 때만 사용할 수 있을 것 같다. 더 좋은 방법이 있을까...

 

트레이스 벡터는 만약 갱신하게 되면 i번 물건을 가져간다는 의미로 인덱스를 넣는다. dp와 거의 유사하게 동작한다.

 

#include<iostream>
#include<vector>
using namespace std;
int N, M;
int dp[101][10001];

int main(){
	cin >> N >> M;

	vector<pair<int, int>> objs(N);
	vector<int> trace[101][300];
	for(int i = 0; i < N; i++){
		cin >> objs[i].first >> objs[i].second;
	}

	for (int i = 1; i <= N; i++){
		int value = objs[i - 1].second;
		int cost = objs[i - 1].first;

		for(int j = 1; j <= M; j++){ // 남은 공부시간
			if(j - cost >= 0){ // 남은 공부 시간을 사용하면 공부 가능
				if(dp[i - 1][j - cost] + value > dp[i - 1][j]){
                	// 사용한 물건 갱신
					trace[i][j] = trace[i - 1][j - cost];
					trace[i][j].push_back(i);

					dp[i][j] = dp[i - 1][j - cost] + value;
				}else{
					trace[i][j] = trace[i - 1][j];
					dp[i][j] = dp[i - 1][j];
				}
			}else{
				dp[i][j] = dp[i][j - 1];
				trace[i][j] = trace[i - 1][j];
			}
		}
	}

	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			cout << i << ", " << j << " ";
			for(int a : trace[i][j]){
				cout << a << " ";
			}
			cout << "    " << dp[i][j];
			cout << endl;
		}
	}

	cout << dp[N][M] << '\n';
}