[백준(Baekjoon)][자바(java)] 12865 : 평범한 배낭 / 동적 계획법 1

 

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

12865번: 평범한 배낭

 

< 풀이 방법 >

▶  물품의 수는 N개, 버틸 수 있는 최대 무게는 K ( 1 ~ K 까지 가능 )

▶  i번째 물품의 무게는 w_i, 가치는 v_i

▶  (N+1)*(K+1) 크기의 2차원 dp배열 생성 ( dp[i][j], 1 <= j <= n, 1<= j <= k )

▶  이중 for문 반복하며 dp[i][j] ( 1 ~ i번째 물품까지 j 무게에 버틸 수 있는 최대 가치합 ) 에 값을 넣음

▶  w_i가 j보다 작거나 같으면 dp[i][j]는 dp[i-1][j] ( i-1번째 물품까지 j 무게를 견딜 수 있는 최대 가치합 ) 와

                                                        dp[i-1][j-(a[i][0])] + a[i][1] ( i-1번째 물품까지 j-w_i 무게를 견딜 수 있는 가치합 + i번째 물품의 가치 ) 

                                                        둘 중 큰 값이 됨

▶  w_i가 j보다 크면 dp[i][j]는 dp[i-1][j] ( i-1번째 물품까지 j 무게를 견딜 수 있는 최대 가치합 ) 이 됨

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), k = sc.nextInt(), i, j;
		int a[][] = new int[n+1][2];
		int dp[][] = new int[n+1][k+1];
		for( i = 1; i <= n; i++ )
			for( j = 0; j < 2; j++ )
				a[i][j] = sc.nextInt();
		
		for( i = 1; i <= n; i++ ) 
			for( j = 1; j <= k; j++ ) 
				dp[i][j] = a[i][0] <= j ? 
					Math.max( dp[i-1][j], dp[i-1][j-(a[i][0])] + a[i][1] ) : 
					dp[i-1][j];
		
		System.out.println( dp[n][k] );
		sc.close();
	}
}