[백준][JAVA]평범한 배낭(12865번) - 다이나믹 프로그래밍, 배낭 문제

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

12865번: 평범한 배낭

* 문제는 해당 게시물 참고바랍니다.

 

해당 문제는 동적 계획법 1에 분류되어 있으며

알고리즘 분류로는 다이나믹 프로그래밍과 배낭 문제에 해당합니다.

 

 다이나믹 프로그래밍이란 흔히 DP라고도 불립니다. 

이는 최적화 이론의 한 기술으로,  특정 범위까지의 값을 구하기 위해서 하나의 큰 문제를 여러개의 작은 문제로 나누어 해당 문제들 값을 이용하여 기존의 하나의 문제를 효율적으로 값을 구하는 알고리즘 설계기법입니다.

 

배낭 알고리즘이란

해당 점화식을 이용하면 쉽게 풀 수 있습니다.

여기서 N - 물건 개수, W - 무게

 

이를 코드 형식으로 이용한다면

bag[i][j] = Math.max(bag[i-1][j],bag[i-1][j-w[i]]+v[i]);

이렇게 표현할 수 있습니다.

 

이제 해당 문제를 해결한 전체 코드입니다.

import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int k = scanner.nextInt();

        int []w = new int[n+1];
        int []v = new int[n+1];

        int [][] bag = new int[n+1][k+1]; 
        
        for(int i=1; i<=n; i++){
            w[i] = scanner.nextInt();
            v[i] = scanner.nextInt();
        }
        
        for(int i=1; i<=n; i++){ 
            for(int j=1; j<=k; j++){ 
                bag[i][j] = bag[i-1][j];
                if(j-w[i] >= 0){
                    bag[i][j] = Math.max(bag[i-1][j],bag[i-1][j-w[i]]+v[i]);
                }
            }
        }
        System.out.println(bag[n][k]);
    }
}

 

결과

 

해당 문제는 배낭 알고리즘의 점화식을 모른다면 정말 풀기 힘들것 같습니다.