링크

12865 평범한 배낭

문제

풀이

유명한 dp문제이다. 못풀어서 블로그를 통해 이해하고 풀었다.
(참조한 블로그 링크 : 도움된 링크)

이런식으로 풀었다.
처음에 처음 물건은 스킵하고 두번째 물건부터 보자면
(4,8)인 경우 무게가 4일때 가방에 담아 8이 들어간다.
가방 무게가 5인 경우도 4일때와 동일하게 8을 넣어준다.
가방 무게가 6인 경우는 (6,13)이 있기 때문에 13이 8보다 크기 때문에 13을 넣어줘야 한다.

세번째 물건인 (3,6)을 보자.
가방 무게가 3일때 6이 들어간다.
가방 무게가 4인 경우 (4,8)이 있어 6보다 8이 크기 때문에 8을 담아준다.
가방 무게가 5인 경우 앞에와 동일하게 8
가방 무게가 6인 경우 (6, 13)이 있기 때문에 큰값인 13을 넣어준다.

무게가 7인 경우 중요하다!
(3,6)을 넣고 (4,8)을 넣을 수 있기 때문에 최댓값인 14가 된다. 그러므로 주의해줘야 한다.
처음에 작성한 코드는

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


public class Test4{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] arr = br.readLine().split(" ");
        int n = Integer.parseInt(arr[0]);
        int k = Integer.parseInt(arr[1]);

        int[] weights = new int[n+1];
        int[] values = new int[n+1];
        int[][] dp = new int[n+1][k+1];


        for(int i=1;i<n+1;i++){
            arr = br.readLine().split(" ");

            int a = Integer.parseInt(arr[0]);
            int b = Integer.parseInt(arr[1]);

            weights[i] = a;
            values[i] = b;
        }

        for(int i=1;i<dp.length;i++){
            int currentWeight = weights[i];
            int currentValue = values[i];

            for(int j=1;j<dp[i].length;j++){
                //앞에꺼 저장
                dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);

                if(j - currentWeight >= 0){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j - currentWeight] + currentValue);
                }


            }
        }

        System.out.println(dp[n][k]);


    }

}

이 코드였다 2중 for문 안에 if(j - currentWeight >=0)인 부분을 보자

if(j - currentWeight >= 0){
    dp[i][j] = Math.max(dp[i][j], dp[i][j - currentWeight] + currentValue);
}

Math.max부분에 dp[i][j-currentWeight] + currentValue)를 하게 되면
input
5 14
1 5
2 3
3 6
4 7
5 8

answer
26

이렇게 (1,5)인 경우 가방무게가 1씩 늘어날때마다 계속 물건을 집어넣는 문제가 생겨버린다.

그래서 이 문제를 해결하는 방법은 dp[i-1][j-currentWeight] + currentValue로 작성하게 되면
(1,5)에서 i-1인 부분은 싹다 0이기 때문에 5 5 5 ... 이렇게 저장된다.

코드

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


public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] arr = br.readLine().split(" ");
        int n = Integer.parseInt(arr[0]);
        int k = Integer.parseInt(arr[1]);

        int[] weights = new int[n+1];
        int[] values = new int[n+1];
        int[][] dp = new int[n+1][k+1];


        for(int i=1;i<n+1;i++){
            arr = br.readLine().split(" ");

            int a = Integer.parseInt(arr[0]);
            int b = Integer.parseInt(arr[1]);

            weights[i] = a;
            values[i] = b;
        }

        for(int i=1;i<dp.length;i++){
            int currentWeight = weights[i];
            int currentValue = values[i];

            for(int j=1;j<dp[i].length;j++){
                //앞에꺼 저장
                dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);

                if(j - currentWeight >= 0){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j - currentWeight] + currentValue);
                }


            }
        }

//        for(int i=0;i<dp.length;i++){
//            System.out.println(Arrays.toString(dp[i]));
//        }

        System.out.println(dp[n][k]);


    }

}