[알고리즘] 백준 12865 평범한 배낭 -dp-

 

 

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

12865번: 평범한 배낭

 

 

백준 동적계획법1 단계별 풀기 마지막 문제인 평범한 배낭 문제를 풀어보았습니다 ㅎㅎ

 

풀다가 도저히 모르겠어서 아래 사이트를 참고해서 풀이했습니다. (설명도 매우 잘되어있었습니다.!)

https://fbtmdwhd33.tistory.com/60

[백준,BOJ 12865] 평범한 배낭(JAVA 구현)

 

 

 

풀이는 다음과 같습니다.

[java[

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); //물품의수
        int K = sc.nextInt(); //준서가 버틸수 있는 무게
        int[][] dp = new int[N + 1][K + 1]; //[물품인덱스][무게] = 최대가치
        int[] w = new int[N + 1]; //무게
        int[] v = new int[N + 1]; //가치
        for (int i = 1; i <= N; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }

        for (int i = 1; i <= N; i++) { //아이템 순
            for (int j = 1; j <= K; j++) { //버틸수있는 무게(j)
                dp[i][j] = dp[i - 1][j];
                if (j - w[i] >= 0) { //들어갈 수 있는 무게인 경우
                    //이전아이템까지의 최대가치 vs 현재아이템의 최대 가치 + 현재아이템의 남은 무게에서의 최대가치
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
                }
            }
        }
        System.out.println(dp[N][K]);

    }
}

https://github.com/mtjin/algorithm_practice/tree/master/%EB%B0%B1%EC%A4%80%2012865%20%ED%8F%89%EB%B2%94%ED%95%9C%20%EB%B0%B0%EB%82%AD%20-dp-

mtjin/algorithm_practice

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다!!