[BAEKJOON] 12865

※ 소스코드는 각 문제 설명 하단에 <더보기>를 통해 확인하실 수 있습니다.

 

[gold 5, 12865 평범한 배낭] - 0/1 Knapsack

흔히 배낭 문제들은 1)짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 2)짐을 쪼갤 수 없는 경우(0이상의 정수)로 나뉜다
1) 짐을 쪼갤 수 있는 경우를 분할 가능 배낭 문제(Fractional)
2) 짐을 쪼갤 수 없는 경우를 배낭 문제(0/1 Knapsack)라 부른다
 
0/1 Knapsack은 다음과 같이 점화식이 정해져 있다(i= 물건 번호, j= 현재 배낭무게)

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]]) + V[i];

단, 점화식에서 현재 배낭무게와(j)와 현재 물건의 무게(W[i])의값의 차가 음수가 될 수 있으므로, 이 경우에는 이전 배열의 값을 넣어준다

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];

점화식을 활용해 문제를 풀어나갈 때, 물건 번호 및 배낭무게를 저장 또는 탐색할 배열의 시작 인덱스는 1이어야 함에 유의한다

#include <iostream>
#include <algorithm>
#pragma warning(disable:4996)

using namespace std;

int N, K;
int W[101], V[101];
int dp[101][100001];

int main() {
	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 (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];
		}
	}
	printf("%d", dp[N][K]);
}