냅색 문제 12865 배낭

2022. 12. 29. 11:53boj

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

 

12865번: 평범한 배낭

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)

www.acmicpc.net

이문제의 경우 

01 냅색 문제로 대표적인 내용이라고 한다.

여기서 처음 나는 선택을 할지 안할지를 1차원 배열을 기준으로 두고 

문제를 해결하려고 하였다.

 

void solve(vector<vector<int>>& v, int idx, int val, int sum, int w) {
	if (sum > w) {
		return ;
	} 
	if (dp[sum] != 0) {
		if (dp[sum] < val) {
			dp[sum] = val;
		} else {
			return ;
		}
	}
	for (int i = idx; i < v.size(); ++i) {
		if (sum + v[i][0] <= w) {
			solve(v, i + 1, val + v[i][1], sum + v[i][0], w);
			if (dp[sum + v[i][0]] < val + v[i][1])
				dp[sum + v[i][0]] = val + v[i][1];
		}
	}
}

처음 로직은 위와 같았는데 값을 선택할 수 있으면 선택해서 미리 저장된 값이 존재하는지 확인한 후 

크다면 변경하고 아니면 그만두는 로직을 선택하였다. 허나 위와 같은 코드는 제출하니 37% 정도에서 막히는것을 확인 할 수 있었고

여러 사람들에게 2차원으로 해결하라는 이야기를 듣게 되었다.

따라서 비슷한 로직으로 이전의 값을 가지고 더해서 체크하는 로직을 처리할 수 있도록 

void solve(vector<vector<int>>& v, int n, int w) {
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j <= w; ++j) {
			if (j + v[i - 1][0] <= w) {
				dp[i][j + v[i - 1][0]] = max(
					dp[i - 1][j + v[i - 1][0]], dp[i - 1][j] + v[i - 1][1]
				);
			}
		}	
	}
}

위와 같이 처리하는 함수를 만들었고 동작시켰다 . 이또한 문제가 발생하였는데 왜 문제가 발생하였는지는 찾을 수 없엇고 

혹시나 하는 마음에 이전의 값을 미리 저장을 시켜두는 로직을 추가하게 되었다.

 

void solve(vector<vector<int>>& v, int n, int w) {
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j <= w; ++j) {
			if (j + v[i - 1][0] <= w) {
				dp[i][j + v[i - 1][0]] = max(
					dp[i - 1][j + v[i - 1][0]], dp[i - 1][j] + v[i - 1][1]
				);
			}
		}	
		for (int j = 1; j <= w; ++j) {
			dp[i][j] = max(dp[i - 1][j], dp[i][j]);
		}
	}
}

이렇게 로직을 작성하니 통과하였는데 아직 3 코드의 차이를 정확하게 찾지 못하였다. 알고 계시는 분은 

댓글남겨주신다면 너무 감사할 것 같다.

 

'boj' 카테고리의 다른 글

1181cpp 문제 해결.  (0) 2022.12.30
boj 11000번. 강의실 배정.  (0) 2022.12.29
별찍기-10 2447  (3) 2022.12.26
1920 수찾기.  (0) 2022.12.25
보물  (0) 2022.12.25