백준 12865 c++ "평범한 배낭" -PlusUltraCode-

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

 

 

 

 

 

 

 

[필자 사고]

Dp문제이다.

Dp문제에서 핵심은 Dp를 어떻게 정의하느냐에 있다고 생각한다.

 

필자는 Dp[i][k] 라고 선언했고 k는 무게를 의미하며 i는 가방의 종류를 의미한다. Dp값은 최대 가치를 의미한다.

 

 max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i])이 코드가 핵심이라고 생각한다.

 

현재의 가방의 최대치를 구하기 위해 먼저 해당 가방의 무게가 k를 넘지 않아야 된다.

 

다음으로 생각할 것은 현재 가방에 넣은 물건들의  가치 최대치이다.

 

1. 만약 해당 가방의 무게가 k보다 작은경우에서

 

     이전 Dp[i-1][j] 의 가치가 높은지 아니면 Dp[i-1][j-W[i]]+V[i] 높은지 비교하는것이다.

 

2. k보다 큰경우는

 

    Dp[i][j] = Dp[i-1][j] 를 넣어주면 된다.

 

[소스 코드]

#include <iostream>
#include <vector>


using namespace std;

int N, K;
vector<int> W;
vector<int> V;
vector<vector<int>> Dp;


void Input() {
	cin >> N >> K;
	W.resize(N+1 );
	V.resize(N+1 );
	Dp.resize(N+1 );
	for (int i = 0; i <= N; i++) {
		 Dp[i].resize(K+1);
	}
	for (int i = 1; i <= N; i++) {
		cin >> W[i] >> V[i];
	}
}

void Solve() {
	
	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= K; k++) {
			if (k >= W[i]) {
				Dp[i][k] = max(Dp[i - 1][k], Dp[i - 1][k - W[i]] + V[i]);
			}
			else Dp[i][k] = Dp[i - 1][k];
		}
	}
}

int main(void) {
	Input();
	Solve();
	cout << Dp[N][K];
}