[백준] 12865 평범한 배낭 JAVA

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

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

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

예제 입력 1

4 7
6 13
4 8
3 6
5 12

예제 출력 1

14

출처
문제를 만든 사람: Acka
데이터를 추가한 사람: kpqi5858, leedongbin, riroan, skyoliver

---

이건 dp 문제 !

동적계획법(DP : Dynamic Programming)

• 작은 문제들을 풀면서 그 결과를 저장해 나아가면서 전체 문제를 해결하는 알고리즘을 의미

---

이 문제를 동적 프로그래밍으로 사용한 이유
--> 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

💡 dp에 담을 내용은 가치의 최댓값, dp에 담아야하는 내용은 언제나 답이 포함되어야 한다

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 입력 받기
        int N = scanner.nextInt(); // 아이템의 개수
        int K = scanner.nextInt(); // 배낭의 최대 무게

        int[] weights = new int[N]; // 각 아이템의 무게
        int[] values = new int[N];  // 각 아이템의 가치

        for (int i = 0; i < N; i++) {
            weights[i] = scanner.nextInt();
            values[i] = scanner.nextInt();
        } // i값을 사용하여 물건의 무게와 가치를 입력 받는 과정을 반복

        // 동적 프로그래밍을 위한 2차원 배열 초기화
        int[][] dp = new int[N + 1][K + 1];

        // DP 테이블 채우기
        for (int i = 1; i <= N; i++) {
            for (int w = 1; w <= K; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        // 결과 출력
        System.out.println(dp[N][K]);

        scanner.close();
    }
}

Scanner sc : 키보드에서 입력된 문자열을 읽어들이는 객체
System.in : 입력장치(키보드)를 말한다

 // 동적 프로그래밍을 위한 2차원 배열 초기화
        int[][] dp = new int[N + 1][K + 1];

✅ 2차원 배열을 사용하는 이유 : 특정 문제에서 상태를 더 구체적으로 기록하고 관리할 필요가 있기 때문

배낭 문제의 목표는 주어진 무게 제한 내에서 최대 가치를 얻을 수 있는 아이템 조합을 찾는 것입니다. 여기서 2차원 배열 dp[i][w]는 다음을 의미합니다:

i번째 아이템까지 고려했을 때: 
즉, 첫 번째부터 i번째 아이템까지 선택할 수 있는 상황을 의미합니다.
가방의 무게가 w일 때: 
가방이 특정 무게 w를 수용할 수 있을 때의 최대 가치를 의미합니다.
따라서 dp[i][w]는 "첫 번째부터 i번째 아이템까지 고려하고, 가방의 최대 무게가 w일 때 얻을 수 있는 최대 가치"를 나타냅니다.

특히 배낭 문제와 같은 동적 프로그래밍 문제에서는 두 가지 주요 요소를 추적해야 한다
1) 아이템 개수 : 현재까지 고려한 아이템의 개수
2) 가방의 무게 : 현재 가방에 담을 수 있는 최대 무게

---

➡️ 핵심

// DP 테이블 채우기
        for (int i = 1; i <= N; i++) {
            for (int w = 1; w <= K; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

Math.max() : Math.max(파라미터 1, 파라미터 2)
: 인자1과 인자2 중 큰 값을 리턴

dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);

• 이 코드는 주어진 아이템을 배낭에 넣을지 말지를 결정하고, 그에 따라 최대 가치를 계산하는 역할