[BOJ]12865_평범한배낭(DP)

문제이름 그대로 냅색알고리즘 문제이다. 

그러나 이전의 동전문제와는 달리 살짝 꼬았다.

물건(동전, 내 짐, 보석 등등) 의 종류가 무한정이라면, dp[] 앞에서부터 탐색해도 된다. 

그러나 개수가 정해져 있을 때(보통은 한개임,,가끔 어려운거는 두세개임)에는 dp[] 뒤에서부터 앞으로 가야 한다.

 

이유는 dp[i] = dp[i-무게]+가치 로 하려할 때 자기자신을 중복해서 쓸 수도 있기 때문임.

 

디피에 적응될 때까지 주기적으로 연습 해야겠다...

 

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

12865번: 평범한 배낭

 

코드는 짧지만 어렵다.

키포인트:

- dp[i]에서 i는 무게를 말함. i키로그람이 내 가방이 담을 수 있는 최대리밋이라면, 그때 담은 물건의 가치를 말한다.

- dp[i] = dp[i-무게]+가치 식을 쓰자. (잘 생각해보면 이해됨)

- 이 때, 같은 물건이 무한대 있지 않으므로 젤 무거운것부터 거꾸로 내려와야 한다.

import java.util.Scanner;

public class BOJ12865_평범한배낭 {

	static int N, K;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		K = sc.nextInt();
		
		int[] dp = new int[K+1];
		for(int i=0; i<N; i++) {
			int weight = sc.nextInt();
			int value = sc.nextInt();
			for(int j=K; j>=weight; j--) {
				dp[j] = Math.max(dp[j],dp[j-weight]+value);
			}
		}
		System.out.println(dp[K]);
	}
}