[백준 DP] 12865번 - 평범한 배낭

12865번 - 평범한 배낭

 

<문제>

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

12865번: 평범한 배낭

 

<문제 풀이>

dp	1	2	3	4	5	6	7
1	0	0	0	0	0	13	13
2	0	0	0	8	8	13	13
3	0	0	6	8	8	13	14
4	0	0	6	8	12	13	14

-> dp[N][K] 

dp[2][6]은 dp[1][6]와 dp[1][2] + 8을 비교하여 더 큰 값을 가져온 것이다. 

여기서 2라는 인덱스 값은 6 - 4(j - W[i])에서 나온 값이다. 만약 1번째에 입력된 아이템의 무게가 2라면 dp[1][2]에 0이 아닌 값이 존재할 수 있다. 

다음 8(V[i])이라는 값은 2번째에 입력된 아이템의 무게를 의미한다. 

dp[3][7]은 dp[2][7]와 dp[2][4] + 6을 비교하여 더 큰 값을 가져온 것이다. 

4는 7에서 입력 받은 아이템의 무게인 3을 뺀 값이다. 마침 이전에 입력된 아이템의 무게가 4이기에 dp [3][7]은 14로 갱신된 것이다. 

 

점화식: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i])

 

<코드>

#include <iostream>
#include <algorithm>
using namespace std;

//0-1 Knapscak 문제 
int N, K;
int dp[101][100001] = { 0, };
int W[100001];
int V[1001];

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

	for (int i = 1; i <= N; i++) {
		cin >> W[i] >> V[i];
		dp[i][W[i]] = V[i];
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			/*dp[i][j] = max({dp[i - 1][j], dp[i][j - 1] , dp[i][j]});
			if ((2 * j - 1) == K && dp[i][j - 1] != 0) {
				dp[i][2 * j - 1] = dp[i][j] + dp[i][j - 1];
			}*/

			if (j - W[i] >= 0) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
			else dp[i][j] = dp[i - 1][j];
		}
	}

	cout << dp[N][K] << endl;
	return 0;
}

 

 

 

2022.12.19