[백준] 12865 - 평범한 배낭

[문제링크]

12865번: 평범한 배낭

 

0. 모든 가방 무게에 대해, n-1번째 물건을 고려한 최적의 선택이 존재한다고 하면,

n번째 물건의 무게가 w, 가치가 v일때 무게 j짜리 가방의 최적해는

  - n번째 물건을 선택하지 않는 경우 ( n-1번의 무게 j짜리 최적해 )

  - n번째 물건을 선택한 경우 ( v + n-1번의 무게 j-w짜리 최적해 )

둘 중 큰 경우이다

 

1. 가상의 무게 0, 가치 0인 물건을 가정한다. ( 첫번째 연산에서 '이전 결과값'의 역할을 한다)

 

2. 첫번째 물건부터 차례대로, 가능한 모든 무게에 대해 넣는 경우와 넣지 않는 경우를 비교해 둘 중 큰 값을 선택한다

 

3. n번째 물건까지 종료한 최종 값이 최적해가 된다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int[][]item = new int[n][2];
		for (int i = 0; i < n; i++) {
			st=new StringTokenizer(br.readLine()," ");
			item[i][0]=pint(st.nextToken());
			item[i][1]=pint(st.nextToken());
		}
        //첫번째 행 / 열의 0 값은 dp 연산에서 사용한다
        int[][]dp = new int[n+1][m+1];
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if(j>=item[i-1][0]) {
                	//넣을 수 있다면 넣는 경우와 안넣는 경우를 비교한다
					dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-item[i-1][0]]+ item[i-1][1]);
				}
				else {
                	//넣지 못한다면 이전 결과 유지
					dp[i][j]=dp[i-1][j];
				}
			}
		}
		
		System.out.println(dp[n][m]);
		
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면