[백준 12865] 평범한 배낭 (01 배낭문제)

 

우선 처음에는 방문여부를 visited를 통해 파악하려고 했다

bitset으로 방문여부를 놓고 비트연산을 통해 특정 물건을 포함한 결과인지 아닌지를 통해 

포함여부를 파악하려고 함

 

근데 2차원 배열로 dp를 만들면 포함여부를 확인하지 않아도 됨

 

---

[2차원 dp배열] 

 

dp[i][k]에서 i번째 줄인 dp[i]는

지금까지 나온 최적의 상황에서 i번째 물건을 포함시키면 어케 바뀔까? 를 보는거임

즉 2차원 배열로 만듦으로써 visited 변수 사용하고 방문여부를 계산하지 않아도 됨

 

이렇게 나뉘는거임

 

1. i번째 이전

i번째 이전 물건들 조합으로

즉 1번부터 i-1번 물건 가지고 나올 수 있는 각 kg마다 최고의 value값

 

2. i번째

1번부터 i-1번 물건 가지고 나올 수 있는 최적의 조합결과에,

즉 지금까지 나온 최적의 결과들에 만약 i번째 물건만 추가하면 어떻게 바뀌는지 확인하는거임

 

분명 i번째를 포함시켰을때 더 높은 value가 될때가 있을거고

그냥 i번째를 포함안시켰을때 즉 그 전 결과가 그대로 최고값이 되는 경우가 있을거임

이건 dp 점화식을 통해 판별되는거임

 

그래서 맨 마지막 번째가 모든 물건들의 조합을 고려한 것임

왜냐하면 맨 마지막 줄 즉 dp[i]번째 배열은 i번째 이전 즉 모든 물건들의 조합으로

계산해본 kg 가방에 들어갈 수 있는 최고의 value 조합들을 구한 것이기 때문

 

---

#include <iostream>
#include <algorithm>

#define SIZE 100001

using namespace std;

int N, K;
int dp[101][SIZE];
int w[101], v[101];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> K;
	for (int i = 1; i <= N; i++) cin >> w[i] >> v[i];
	
	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= K; k++) {
			dp[i][k] = dp[i - 1][k];

			if (k - w[i] >= 0) dp[i][k] = max(dp[i - 1][k], dp[i - 1][k - w[i]] +v[i]);
		}
	}

	for (int k = 1; k <= K; k++) {
		cout << k << " ";
	}
	cout << "\n";
	for (int k = 1; k <= K; k++) {
		cout << dp[N][k] << " ";
	}
    
	return 0;
}