12865번. 평범한 배낭

 

아이디어

dp[i] 를 최대 i 만큼의 무게를 넣을 수 있는 배낭을 맸을 때 넣을 수 있는 물건들 가치의 최대값이라고 정의를 한다면

물건의 무게가 각각 6 4 3 5  그 가치가 각각 13 8 6 12 일 때 dp[i] 는

 

dp[i] = max(dp[i - 6] + 13, dp[i - 4] + 8, dp[i - 3] + 6, dp[i - 5] + 12)

 

라고 볼 수 있다.

 

다만 이 때 주의해야할 점은 같은 물건을 배낭에 여러 번 담을 수는 없다는 것이다.

 

예를 들어 dp[3] 을 계산할 때 무게가 3인 물건을 담는 게 가장 가치가 크게 되는 경우이므로 이미 배낭에 담았는데 dp[6] 을 계산할 때 또 담으면 안 된다는 것이다.

 

이는 각 물건에 대해 dp[i] 를 갱신하는 과정을 i 의 오름차순이 아닌 내림차순으로 수행함으로써 해결이 가능하다.

 

dp[3] -> dp[6] 순서로 계산하면 dp[6] 을 계산할 때 사용된 dp[3] 은 무게 3인 물건을 이미 담았을 수 있지만

dp[6] -> dp[3] 순서로 계산하면 dp[6] 을 계산할 때 사용된 dp[3] 은 무게 3인 물건을 아직 담지 않은 상황이므로 중복해서 물건을 담게 될 일이 없다.

 

 

풀이코드

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

public class _n12865_ {
    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[][] items = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 2; j++) {
                items[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[] dp = new int[K + 1];
        for (int i = 0; i < N; i++) {
            int weight = items[i][0];
            int value = items[i][1];

            for (int j = K; j >= weight; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight] + value);
            }
        }

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