[백준] 12865번: 평범한 배낭

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

12865번: 평범한 배낭

첨에 내가 푼 접근법이 완전 틀려서 ㅠㅠ 결국 인터넷에 검색해서 다른분들 해설을 보고서야 해결했다.

 

DP문제 중 매우 유명한 배낭 문제로, 각각의 무게와 가치가 주어진 N개의 물건이 있을 때, 무게가 K가 넘지 않도록 물건들을 배낭에 넣어서 최대 가치를 구하는 문제이다.

 

접근법은 가치의 최대값을 저장하는 배열 dp[101][100001]을 선언한 뒤, 첫번째 물건부터 해당 물건을 넣었을 때와 넣지 않았을 때를 고려하여 무게별로 가치의 최대값을 구해주면 된다.

 

점화식은(i번째 물건에서 무게가 j일때를 구함)

dp[i][j] = dp[i-1][j] (W[i] > j 일 때)

               max(dp[i-1][j], dp[i-1][j - W[i]] + V[i]) (W[i] <= j 일 때)

 

위 식에서 dp[i-1][j]는 i번째 물건을 넣지 않은 경우, dp[i-1][j - W[i]] + V[i]는 i번째 물건을 넣은 경우가 된다. 둘 중 최대값으로 dp를 업데이트 하는 것

 

이렇게 되면

dp[1][K]에는 첫번째 물건만 고려했을 때의 최대 가치

dp[2][K]에는 첫번째물건 ~ 두번째 물건을 고려했을 때의 최대 가치

dp[3][K]에는 첫번째물건 ~ 세번째 물건을 고려했을 때의 최대 가치

.

.

dp[N][K]에는 첫번째물건 ~ N번째 물건을 고려했을 때의 최대 가치

가 담기게 된다.

 

구현이 익숙해질 때까지 연습하자

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

int dp[101][100001];

int main(void) {
	int N, K;
	int W[101], V[101];

	scanf("%d %d", &N, &K);
	for (int i = 1; i <= N; i++) scanf("%d %d", W + i, V + i);

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			if (W[i] <= j) {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
			}
			else {
				dp[i][j] = dp[i - 1][j];
			}
		}
	}

	printf("%d", dp[N][K]);
}