관리 메뉴

막내의 막무가내 프로그래밍 & 일상

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

알고리즘/DP

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

막무가내막내 2020. 6. 19. 16:53
728x90

 

 

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

 

12865번: 평범한 배낭

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)

www.acmicpc.net

 

 

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

 

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

https://fbtmdwhd33.tistory.com/60

 

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

-내 생각 이 문제의 경우 혼자 풀어보려고 해서 결과는 잘 나오는 것 같은데 어떤 반례에서 걸리는지 계속 오답처리를 받아서 결국 검색을 해봤는데, 이러한 무게와 가치가 함께 주어지는 문제��

fbtmdwhd33.tistory.com

 

 

 

풀이는 다음과 같습니다.

[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

알고리즘 문제풀이 연습. Contribute to mtjin/algorithm_practice development by creating an account on GitHub.

github.com

 

 

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

728x90
Comments