1 분 소요

문제

문제 바로가기

입력

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

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

출력

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

접근방법

동적계획법을 이용한 Knapsack 알고리즘을 이용해서 최대 가치를 구하는 문제다. 이 알고리즘은 현재 물건을 포함할 경우와 포함하지 않을 경우로 나눠서 생각한다. 즉, i번째 물건을 포함할 경우 d[i][j-w[i]] + v[i]이 되고, 포함하지 않을 경우 d[i-1][j]이 된다. 두 가지 중에서 최댓값을 저장해주면 된다. 이 때 d[i][j]는 현재 i번째 물건까지 고려해서 가방 용량이 j일 때의 최대 가치를 나타낸다.

이 과정을 N개의 물건에 대해 반복하면 마지막 물건까지 고려했을 때 가방 용량 K 안에서 얻을 수 있는 최대 가치를 구할 수 있다.

그림으로 이해해보면 다음과 같다.

i, j 1 2 3 4 5 6 7
1
(6, 13)		 0 0 0 0 0 13 13
2
(4, 8)		 0 0 0 8 8 13 13
3
(3, 6)		 0 0 6 8 8 13 14
4
(5, 12)		 0 0 6 8 12 13 14

풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[][] d = new int[N+1][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 = 1; j <= K; j++) {
                d[i][j] = d[i-1][j];
                if(j >= w[i]) {
                    d[i][j] = Math.max(d[i][j], d[i - 1][j - w[i]] + v[i]);
                }
            }
        }

        bw.write(String.valueOf(d[N][K]));
        bw.flush();
        bw.close();
        br.close();
    }
}

댓글남기기

참고