0-1 배낭문제 (0-1 knapsack problem)

dp의 대표적인 유형

이건 그리디로 안풀리는 이유가

10인데

8 8

5 5

4 4

있으면 그리디로 풀면 8이 나오는데

실제 답은 4 5 를 넣은 9임

그래서 모든 경우의 수를 다 해봐야하는

dp로 풀어야함

 

---

1. dp[i][k] = dp[i-1][k]

우선 i번째 물건을 포함하기 전

즉 i-1번째 물건까지 포함시켰을때 kg에 들어갈 수 있는 최고의 조합을 그대로 받는다

 

만약 i번째 물건을 고려했을때보다 고려하지 않았을때가 더 좋은 경우이면

i번째 물건을 고려하지 않았을때 kg에 들어갈 수 있는 최고의 조합이 그대로 오는거고

 

만약 i번째 물건을 포함시켰을때 더 좋은 결과가 나오면

더 좋은 결과가 나왔다고 최신화만 시켜주면 되는 것이기 때문이다

 

만약 i번째 물건을 넣을 수 있는 상황이면 비교해서 최신화 하든지 말든지 하자 스탠스인 것이다

 

그리고 그 코드가 아래 코드임

for (int i = 1; i <= N; i++) {
	for (int k = 1; k <= K; k++) {
		// 우선 전 결과를 존중해준다
        	dp[i][k] = dp[i - 1][k];

		// 근데 만약 i번째 물건을 넣을 수 있고
		if (k - w[i] >= 0) {
        		// 더 좋은 결과가 나오면 최신화해준다
        		dp[i][k] = max(dp[i][k], dp[i - 1][k - w[i]] + v[i]);
    		}
	}
}

 

2. dp[i]의 의미는 i번째까지 고려했을때 나올 수 있는 각 k당 최적의 조합의 결과물임

 

즉 i번째까지 했으면 최종결과가 i번째 줄인 dp[i]이다

왜냐하면 특정 라인을 돌때 그 전꺼까지 모두 비교해서 최적의 정답으로 해당 라인을 채우는 것이기 때문

 

3. dp에서 순서를 신경쓰지 않아도 됨. dp[i][k]는 결과론적인 얘기를 하고 있기 때문이다

 

이게 뭔 말인가 하니

dp[i-1][k-w[i]]]할때 

만약 k-w[i] 배열 일때 해당 물건을 넣고 있었으면 어떡하지?

넣고 있던 중이었으면?

이런 생각을 하지 않아도 되는거라는거임

 

그러니까 dp[i][k]는 결과론적인 얘기를 하고 있는것이다

이미 채워진 것이다.

이미 들어가 있는 것이다.

즉 겹친다 이런 생각을 안해도 된다는거다