백준 BOJ 12865 - 평범한 배낭

말 그대로 평범한 배낭 문제...

 

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

0/1 배낭 문제이다.

dp[i][j] 를 i번째까지 살펴본 배낭의 용량이 j일때의 최대 가치 로 정의하면

풀수 있다.

이 최대 가치를 만드는법은 크게 세가지 경우로 나뉘는데

1) 배낭에 i번째를 넣을수 있고, 넣었음. ( dp[i][j] = dp[i-1][j-w[i]] + v[i] )

2) 배낭에 i번째를 넣을수 있으나, 넣지 않았음. ( dp[i][j] = dp[i-1][j] )

3) 배낭에 i번째를 넣을수 없었기에, 넣지 않았음. ( dp[i][j] = dp[i-1][j] )

 

이 세가지 케이스를 구분해주면 AC를 받을 수 있다.

 

#include <bits/stdc++.h>
using namespace std;

int w[123] = {0};
int v[123] = {0};
int dp[123][123456] = {0}; // dp i, j => i번째까지 살펴본 배낭의 용량이 j일때 가치의 최대. 

int main(){
	int n,k;
	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]) dp[i][j] = max(dp[i-1][j-w[i]] + v[i], dp[i-1][j]); // 넣거나 / 넣지 않거나. 
			else          dp[i][j] = dp[i-1][j]; // 아무것도 넣지 않음. 
		}
	}
	
	printf("%d", dp[n][k]);
	return 0;
}