[백준 12865] 평범한 배낭

문제 출처

1. 구상

• 물건의 무게와 가치를 저장하는 2차원 배열 만들기

• 물건의 경우의 수, 1 ~ 버틸 수 있는 무게까지의 최대 가치를 저장하는 2차원 배열 만들기

• 물건의 무게가 수용 범위보다 무겁다면 전 물건의 최대 가치를 대입
  그렇지 않다면 전 물건의 최대 가치와 (수용 범위 - 현 물건의 무게)의 최대 가치 + 현 물건의 가치를 비교하여 큰 값을 대입
  
  

2. 구현

import java.util.*;
import java.io.*;

public  class Main {	
	
    //최대 가치를 저장하는 배열
	public static int[][] dp;
    //입력받은 물건의 무게, 가치를 저장하는 배열
	public static int[][] arr;
    //물건의 종류
	public static int cnt = 0;
    //물건의 최대 수용 범위
	public static int val = 0;	
	
	public static void main(String[] args) throws Exception {
		Scanner s = new Scanner(System.in);
		
		cnt = s.nextInt();
		val = s.nextInt();
		
        /*수용 범위까지의 최대 가치가 기록되어야 하므로 
        (수용 범위 + 1) 크기로 설정*/
		dp = new int[cnt][val + 1];		
		arr = new int[cnt][2];
		
		for (int i = 0; i < cnt; i++) {
			arr[i][0] = s.nextInt();
			arr[i][1] = s.nextInt();
		}
		
        
		System.out.print(lis(cnt - 1, val));
				
	}
	
	
	
	public static int lis(int i, int k) {
    	//물건의 종류 (0 ~ cnt-1)에 해당하지 않을 경우 0을 반환
		if(i < 0)
			return 0;
		
        //탐색하지 않았다면 아래의 과정 실행
		if (dp[i][k] == 0) {
        	//물건의 무게가 수용 범위보다 무겁다면 전 실행 값을 저장
			if (arr[i][0] > k)
				dp[i][k] = lis(i-1, k);
			
            /*전 실행 값과  
            (수용 범위 - 현 물건의 무게)의 최대 가치 + 현 물건의 가치를 비교*/
			else
				dp[i][k] = Math.max(lis(i-1, k), lis(i-1, k - arr[i][0]) + arr[i][1]);
				
		}
		
		return dp[i][k];
	}
	
} 

코드 및 알고리즘 참고