백준 12865번 - 평범한 배낭

문제

백준 12865번 - 평범한 배낭

아이디어

• dp[i]를 i 무게일 때 가능한 최대 가치로 가정한다.
• 각 무게는 여러 가지 조합에 의해 가능하다.
• 예를 들어 최대 무게(k)가 7일 때, 7, 1+6, 2+5, 3+4 등의 무게 조합이 있을 수 있다.
• 각 물건의 무게에 대해 딱 맞는 무게로 하는 것과 조합에 의해 배낭을 채우는 것 중 최댓값을 갱신해나간다.

예상 시간 복잡도

• 모든 물건(N)에 대해 버틸 수 있는 무게(K)만큼 탐색한다.
• 예상 시간 복잡도 : O(N * K)

코드 구현

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

public class BJ_12865 {
    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());

        int[] dp = new int[k + 1];
        int[] w = new int[n + 1]; //각 물건 무게
        int[] v = new int[n + 1]; //각 물건 가치

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

            w[i] = Integer.parseInt(st.nextToken());
            v[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 1; i <= n; i++) {
            for (int j = k; j - w[i] >= 0; j--) {
                dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]); //조합 가능한 무게의 가치 + 현재 무게의 가치
            }
        }

        System.out.println(dp[k]);
    }
}