백준 12865 JAVA : 평범한 배낭

문제

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

12865번: 평범한 배낭

 

풀이 예상

dp 배열을 이용해서 N번째 물품까지 사용했을 때 K무게에서의 최대가치를 갱신해주면 된다.

물품을 받고, K를 늘려가면서 물건을 넣지 않은 전 값과 물건을 넣고나서의 최대값을 비교하면서 갱신

 

예제를 예시로 들면

입력
4 7
6 13
4 8
3 6
5 12

 

1. W : 6, V : 13 물품

W(6) 값 부터 물품을 넣을 수 있으니까 6, 7 무게에 넣어준다.

 

 

2. W : 4, V: 8 물품

 

W(4)값 부터 물품을 넣을 수 있으니까 4, 5 무게에는 V(8) 값을 넣어준다.

6, 7 무게는 이미 위치한 13 값이 더 크므로 13을 넣어준다.

 

3. W : 3, V: 6 물품

W(3)값 부터 물품을 넣을 수 있으니까 3 무게에는 V(6) 값을 넣어준다.

4, 5, 6 무게는 이미 위치한 값이 더 크므로 위치한 값들을 넣어준다.

7무게는 현재 물품의 가치(6)와 무게가 4인 물품의 가치(8) 를 합한 것이 더 크므로 14값을 넣어준다.

 

3. W : 5, V: 12 물품

W(5) 값 부터 물품을 넣을 수 있으니까 이전값들(3, 4 무게 값)은 그대로 가져오고

5 무게는 이미 위치한 값보다 현재 가치(12) 가 더 크므로 현재 가치로 넣어준다.

6, 7 무게는 이미 위치한 값들이 현재물품으로 조합할 수 있는 값보다 더 크므로 그대로 넣어준다.

 

이런 로직을 반복하면 마지막 backpack[N][K] 에 위치한 값이 최대 가치가 될 수 있다.

 

풀이방법 (접근 방법 & 시간복잡도)

시간복잡도 => O(NK)

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

public class Main {
    static int W,V;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[][] backpack = new int[N+1][K+1]; //N번째 물품을 넣었을 때, K무게에서의 최대 가치

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            W = Integer.parseInt(st.nextToken());
            V = Integer.parseInt(st.nextToken());

            for (int j = 1; j <= K; j++) {
                backpack[i][j] =  backpack[i-1][j]; //이전 값 저장
                if(j - W >=0) { //물건을 넣을 수 있으면
                    //물건을 넣은 최대값과 물건을 넣지 않은 전값을 비교
                    backpack[i][j] = Math.max(backpack[i-1][j-W]+V, backpack[i-1][j]);
                }

            }

        }
        System.out.println(backpack[N][K]);


    }
}

 

결과