[백준] 12865번 평범한 배낭 _ JAVA ( 주석 설명 )

풀이

1) dp 정의

- dp[n][k] : 각 무게에서 n번째 물건까지 담을 경우(담을 수 있는지 판별 후) 가질 수 있는 최대 가치를 저장

행 : n번째 물건

열 : 무게 k



2) 점화식

if(k - W[n] >= 0) // 담을 수 있다.

	dp[n][k] = Math.max(dp[n-1][k], V[n] + dp[n-1][k - W[n]];

else

	dp[n][k] = dp[n-1][k];

 

https://st-lab.tistory.com/141

https://fbtmdwhd33.tistory.com/60

 

---

 

1번

→ Top-down 방식

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

public class Main {
    static int W[]; //물건의 무게를 담는 배열
    static int V[]; //물건의 가치를 담는 배열

    //각 인덱스가 각 물건마다 가질 수 있는 최대 가치를 담는 배열
    static Integer dp[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); //물품의 수
        int K = Integer.parseInt(st.nextToken()); //최대로 담을 수 있는 무게

        W = new int[N+1];
        V = new int[N+1];

        //이전 물건에 대한 가치를 메모제이션 할 때, 0번째 물건 가치를 저장하기 위해 N+1 공간
        //무게 K 일 때 최대 가치를 알아내기 위한 K+1 공간을 생성한다.
        dp = new Integer[N+1][K+1];

        //0번째 물건 가치를 비워두기 위해(0) 1부터 시작한다.
        for(int i=1;i<=N;++i){
            st = new StringTokenizer(br.readLine());

            W[i] = Integer.parseInt(st.nextToken()); //물건 무게
            V[i] = Integer.parseInt(st.nextToken()); //물건 가치
        }

        System.out.println(solve(N, K));
    }

    //Top-down 방식
    private static int solve(int N, int K) {
        //이전 값 0번째 물건에 대한 가치는 0이다.
        if(N==0)
            return 0;
        if(dp[N][K] == null){
            //물건을 담을 수 있는 경우
            if(K-W[N]>=0){
                //이전 가치 vs 현재 무게의 가치 + 이전 값에 대한 남은 무게( K-W[N] )에 대한 가치 를 비교한다.
                dp[N][K] = Math.max(solve(N-1,K), V[N] + solve(N-1, K-W[N]));
            }

            //물건을 추가로 담을 수 없는 경우
            else{
                dp[N][K] = solve(N-1, K);
            }
        }

        return dp[N][K];
    }
}

 

---

 

2-(1)번

→ Bottom-up 방식

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

public class Main {
    static int W[]; //물건의 무게를 담는 배열
    static int V[]; //물건의 가치를 담는 배열

    //각 인덱스가 각 물건마다 가질 수 있는 최대 가치를 담는 배열
    static int dp[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); //물품의 수
        int K = Integer.parseInt(st.nextToken()); //최대로 담을 수 있는 무게

        W = new int[N+1];
        V = new int[N+1];

        //이전 물건에 대한 가치를 메모제이션 할 때, 0번째 물건 가치를 저장하기 위해 N+1 공간
        //무게 K 일 때 최대 가치를 알아내기 위한 K+1 공간을 생성한다.
        dp = new int[N+1][K+1];

        //0번째 물건 가치를 비워두기 위해(0) 1부터 시작한다.
        for(int i=1;i<=N;++i){
            st = new StringTokenizer(br.readLine());

            W[i] = Integer.parseInt(st.nextToken()); //물건 무게
            V[i] = Integer.parseInt(st.nextToken()); //물건 가치
        }

        solve2(N, K);
        System.out.println(dp[N][K]);
    }

    private static void solve2(int N, int K){
        for(int i=1;i<=N;++i){ //N번째 물건
            for(int j=1;j<=K;++j){ //각 무게에서 가질 수 있는 최대 가치
                //물건을 넣을 수 있으면
                if(W[i]<=j){
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-W[i]] + V[i]);
                }
                //물건을 추가할 수 없으면
                else
                    dp[i][j] = dp[i-1][j];
            }
        }
    }
}

 

---

 

2-(2)번

→ Bottom-up 방식

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

public class Main {
    static int W[]; //물건의 무게를 담는 배열
    static int V[]; //물건의 가치를 담는 배열

    //각 인덱스가 각 물건마다 가질 수 있는 최대 가치를 담는 배열
    static int dp[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); //물품의 수
        int K = Integer.parseInt(st.nextToken()); //최대로 담을 수 있는 무게

        W = new int[N+1];
        V = new int[N+1];

        //이전 물건에 대한 가치를 메모제이션 할 때, 0번째 물건 가치를 저장하기 위해 N+1 공간
        //무게 K 일 때 최대 가치를 알아내기 위한 K+1 공간을 생성한다.
        dp = new int[K+1];

        //0번째 물건 가치를 비워두기 위해(0) 1부터 시작한다.
        for(int i=1;i<=N;++i){
            st = new StringTokenizer(br.readLine());

            W[i] = Integer.parseInt(st.nextToken()); //물건 무게
            V[i] = Integer.parseInt(st.nextToken()); //물건 가치
        }

        solve3(N, K);
        System.out.println(dp[K]);
    }

    private static void solve3(int N, int K){
        for(int i=1;i<=N;++i){ //N번째 물건

            //무계의 한계치까지 반복 수행한다.
            //각 무게에서 가질 수 있는 최대 가치
            for(int j=K;j-W[i]>=0;--j){
                //N번째 무게의 가치 + 남은 무게의 가치가 크다면 그 값을 갱신해준다.
                dp[j] = Math.max(dp[j], dp[j-W[i]] + V[i]);
            }
        }
    }
}

 

 

---

* 잘못된 접근

dp[] : '각 무게가 가질 수 있는 최대 가치' 으로 정의하고

dp[5] 이라면 Math.max(dp[1] + dp[4], dp[2] + dp[3]) 방식으로 접근했으나

1개의 물건이 중복적으로 담겨지는 것을 확인하고 실패...

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

public class Main {
    static int ary[][]; //물건의 무게와 가치를 담는 배열
    static Integer dp[]; //각 인덱스가 담을 수 있는 최대 무게라 가정하고, 가질 수 있는 최대의 가치를 담는 배열
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); //물품의 수
        int K = Integer.parseInt(st.nextToken()); //최대로 담을 수 있는 무게

        ary = new int[N][2];
        //K의 무게까지 표현할 수 있어야한다.
        //입력되는 물건의 무게가 없는 것들은 무게를 0으로 산정해야한다. (int 배열을 사용하면 '0'의 의미가 생기므로 dp[] 메모제이션 체크 불가)
        //Integer 배열로 선언해 무한 반복을 피한다.
        dp = new Integer[K+1];

        for(int i=0;i<N;++i){
            st = new StringTokenizer(br.readLine());

            ary[i][0] = Integer.parseInt(st.nextToken()); //물건 무게
            ary[i][1] = Integer.parseInt(st.nextToken()); //물건 가치

            if(dp[ary[i][0]] == null)
                dp[ary[i][0]] = ary[i][1];
            else{ //동일한 무게이나 가치가 더 높은 물건이 나올 시 가치를 갱신해준다.
                dp[ary[i][0]] = Math.max(dp[ary[i][0]], ary[i][1]);
            }
        }

        System.out.println(solve(K));

        for(int i=0;i<=K;++i){
            System.out.println(dp[i]);
        }
    }

    private static int solve(int K) {
        if(dp[K]==null) { //dp[K]가 메모제이션이 안 되어 있으면 계산을 시작한다.
            dp[K] = 0; //기본적으로 'K'의 무게를 가진 물건(가치)가 없으므로 0으로 설정한다.

            //K가 짝수일 때 : 중앙값이 두 번 사용된다,
            int range_K = (K%2==0) ? K/2 : K/2+1;
            for (int i = 1; i < range_K; ++i) { //(K/2) 이후는 중복 계산이므로 생략한다.
                dp[K] = Math.max(dp[K], solve(K-i) + solve(i));
            }
        }

        return dp[K];
    }
}