여행 짐 싸기

풀이

완전 탐색 알고리즘

물건의 모든 조합을 하나한 검사하고 이들 중 최적의 조합을 찾아내는 완전 탐색 알고리즘을 작성해 봅시다. 각 물건에 대해 가져가거나 말거나 두 가지의 선택이 있으므로 전체 $2^n$개의 조합이 있습니다. 다음과 같은 부분 문제를 얻을 수 있습니다.

$pack(items)$=지금까지 고른 물건들의 목록이 $items$에 주어질 때, 남은 용량을 채워 얻을 수 있는 최대의 절박도 합

동적 계획 법 알고리즘

최적화 문제를 위한 동적 계획법 레시피를 돌이켜 봅시다. $items$를 넣고 남은 용량에 담을 수 있는 물건들의 절박도 합만을 반환하도록 $pack()$을 바꾸면, 지금까지 고른 물건들의 목록은 상관이 없습니다. 중요한 것은 마지막으로 고른 물건의 번호(같은 물건을 두 번 고르면 안 되니까)와 캐리어에 남아 있는 용량이죠. 그러면 다음과 같은 형태의 부분 문제를 얻을 수 있습니다.

$pack(capacity, item)$=캐리어에 용량이 $capacity$만큼 남았을 때 $item$ 이후의 물건들을 싸서 얻을 수 있는 최대 절박도

이때 각 물건에 대해 우리가 할 수 있는 선택은 가져간다 / 가져가지 않는다의 둘입니다. 각 경우의 최대 절박도를 다음과 같이 계산할 수 있습니다.

• 해당 물건을 가져가는 경우: $pack(capacity-volume[item], item + 1)+need[item]$
• 해당 물건을 가져가지 않는 경우: $pack(capacity, item + 1)$

구현

완전 탐색에 메모이제이션을 적용한 것입니다.

import java.util.*;

public class Main {

    public static int n, capacity;
    public static int[] volume, need;
    public static int[][] cache;
    public static String[] name;
    public static int sum;
    public static ArrayList<String> picked;

    public static void input(Scanner scanner) {
        n = scanner.nextInt();
        capacity = scanner.nextInt();
        volume = new int[n];
        need = new int[n];
        cache = new int[capacity + 1][n];
        name = new String[n];

        for (int i = 0; i < n; i++) {
            name[i] = scanner.next();
            volume[i] = scanner.nextInt();
            need[i] = scanner.nextInt();
        }

        for (int i = 0; i < cache.length; i++) {
            Arrays.fill(cache[i], -1);
        }
    }

    public static void solve() {
        sum = pack(capacity, 0);
        picked = new ArrayList<>();
        reconstruct(capacity, 0, picked);
    }

    // 캐리어에 남은 용량이 capacity일 때, item 이후의 물건들을 담아 얻을 수 있는 최대 절박도의 합을 반환하는 메소드
    public static int pack(int capacity, int item) {
        // 기저 사례: 더 담을 물건이 없을 대
        if (item == n) return 0;
        if (cache[capacity][item] != -1) return cache[capacity][item];
        // 이 물건을 담지 않을 경우
        cache[capacity][item] = pack(capacity, item + 1);
        // 이 물건을 담을 경우
        if (capacity >= volume[item])
            cache[capacity][item] = Math.max(cache[capacity][item], pack(capacity - volume[item], item + 1) + need[item]);
        return cache[capacity][item];
    }

    // pack(capacity, item)이 선택한 물건들의 목록을 picked에 저장하는 메소드
    public static void reconstruct(int capacity, int item, ArrayList<String> picked) {
        // 기저 사례: 모든 물건을 다 고려했음
        if (item == n) return;
        if (pack(capacity, item) == pack(capacity, item + 1)) {
            reconstruct(capacity, item + 1, picked);
        } else {
            picked.add(name[item]);
            reconstruct(capacity - volume[item], item + 1, picked);
        }
    }

    public static void output() {
        System.out.println(sum + " " + picked.size());
        for (String name : picked) {
            System.out.println(name);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        for (int i = 0; i < testCase; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}

시간 복잡도 분석

$pack()$의 $capacity$ 인수는 $[0, w]$ 범위의 값을 가질 수 있고, $item$ 인수는 $[0, n)$ 범위의 값을 가지니 존재하는 부분 문재의 수는 $O(nw)$입니다. 각 부분 문제를 해결하는 데는 상수 시간이면 충분하니 이 알고리즘의 시간 복잡도는 전체 $O(nw)$이죠.

회고