[백준 12865] 평범한 배낭 (JAVA)

백준 12865번 문제 - 평범한 배낭

12865번: 평범한 배낭

---

문제 분석

 

 

• 배낭에 넣을 수 있는 무게는 정해져있다. 
• 배낭에 담을 수 있는 가치에 최댓값을 출력해라

---

해결 키 포인트

 

• DP 문제
• 첫 번째 풀때는 정렬을 하면 더 편리할 거라 생각했지만 아니었다.
• 무게와 가치를 한번에 관리하기 위해 클래스 제작 : Product
• 최대 가치를 알기 위해 누적 값을 보관할 dp 필요
  • dp는 2차원 배열로 생성
  • 처음에 dp도 무게에 따른 최대 가치를 알아내면 되기때문에 Product를 K개 만큼 만들려 했지만 실패
  • WHY? dp에는 현재 물건 전에 계산된 무게 값도 필요하기 때문
    → i번째 product를 이용했을 때 j 무게의 최대 가치 뿐만 아니라 i-1번째 product를 이용했을 때 j 무게의 최대 가치  
• 무게 확인은 1부터 
  • 처음에 무게를 어차피 이전꺼는 안되니까 product의 무게부터 확인했는데 그러면 전에 product와 연동이 안됨
• 현재 값을 넣을 수 있는 무게일 경우 - 다음 코드로 최대값 구하기

// 현재 무게와 현재값을 넣을 수 있는 최대값 + 현재값 중에 큰 값으로 설정
dp[i][j] = Math.max(dp[i][j], dp[i-1][j-p.w] + p.v);

 

---

코드

 

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

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        List<Product> products = new ArrayList<>();

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

            int w = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            products.add(new Product(w,v));
        }

        // dp[i][j] : i번째 입력된 값에 대해 무게가 j일 때 최대 가치
        int [][] dp = new int [N+1][K+1];

        for (int i = 1; i <= N; i++) {
            Product p = products.get(i-1);
            // 무게 1 부터 확인
            for(int j=1; j<=K; j++) {
                dp[i][j] = dp[i-1][j];
                // 만약 현재 값을 넣을 수 있는 무게일 경우
                if(j - p.w >= 0) {
                    // 현재 무게와 현재값을 넣을 수 있는 최대값 + 현재값 중에 큰 값으로 설정
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-p.w] + p.v);
                }
            }
        }

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

    public static class Product {
        int w;
        int v;
        public Product(int w, int v) {
            this.w = w;
            this.v = v;
        }
    }
}