[BJ] 12865 : 평범한 배낭

       문제 요약        

- 문제

 

- 입출력

입력

출력

         아이디어        

 

dp[n][k] : 가방 무게를 k만큼 고려했을 때, n번째 아이템을 선택/비선택했을 때 최대 가치

 

         소스코드        

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

public class Main { //평범한 배낭
    static int N, K;
    static int[][] dp; // 가방무게 K까지 고려했을 때, 최대가치
    static int[] weight;
    static int[] value;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 물품의 수
        K = Integer.parseInt(st.nextToken()); // 가방 무게 K
        weight = new int[N+1];
        value = new int[N+1];

        for (int n = 1; n <= N; n++) {
            st = new StringTokenizer(br.readLine());
            weight[n] = Integer.parseInt(st.nextToken());
            value[n] = Integer.parseInt(st.nextToken());
        }

        // dp[n][k] : 가방무게를 k만큼 고려했을 때, n번째 아이템을 선택/비선택했을 때 최대가치
        dp = new int[N + 1][K + 1];
        for (int i = 1; i <= N; i++) { // 아이템 i번째 선택
            for (int k = 1; k <= K; k++) { //가방 무게가 1 ~ K 까지 고려
                dp[i][k] = dp[i - 1][k];
                if (k - weight[i] >= 0)
                    dp[i][k] = Math.max(dp[i - 1][k - weight[i]] + value[i], dp[i - 1][k]);
                // Math.max(i번째 item을 선택할 경우 최대 가치, 선택하지 않을 경우 최대 가치)
                // i번쨰 item을 선택 : i-1번째 item, (k - i번째 item의 무게)가방 무게까지 고려했을 때 최대가치 + i번째 item의 무게
            }
        }
        System.out.println(dp[N][K]);
    }
}