문제 풀이 - 여행 짐 싸기(JAVA)
풀이
완전 탐색 알고리즘
물건의 모든 조합을 하나한 검사하고 이들 중 최적의 조합을 찾아내는 완전 탐색 알고리즘을 작성해 봅시다. 각 물건에 대해 가져가거나 말거나 두 가지의 선택이 있으므로 전체 개의 조합이 있습니다. 다음과 같은 부분 문제를 얻을 수 있습니다.
=지금까지 고른 물건들의 목록이 에 주어질 때, 남은 용량을 채워 얻을 수 있는 최대의 절박도 합
동적 계획 법 알고리즘
최적화 문제를 위한 동적 계획법 레시피를 돌이켜 봅시다. 를 넣고 남은 용량에 담을 수 있는 물건들의 절박도 합만을 반환하도록 을 바꾸면, 지금까지 고른 물건들의 목록은 상관이 없습니다. 중요한 것은 마지막으로 고른 물건의 번호(같은 물건을 두 번 고르면 안 되니까)와 캐리어에 남아 있는 용량이죠. 그러면 다음과 같은 형태의 부분 문제를 얻을 수 있습니다.
=캐리어에 용량이 만큼 남았을 때 이후의 물건들을 싸서 얻을 수 있는 최대 절박도
이때 각 물건에 대해 우리가 할 수 있는 선택은 가져간다 / 가져가지 않는다의 둘입니다. 각 경우의 최대 절박도를 다음과 같이 계산할 수 있습니다.
- 해당 물건을 가져가는 경우:
- 해당 물건을 가져가지 않는 경우:
구현
완전 탐색에 메모이제이션을 적용한 것입니다.
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();
}
}
}
시간 복잡도 분석
의 인수는 범위의 값을 가질 수 있고, 인수는 범위의 값을 가지니 존재하는 부분 문재의 수는 입니다. 각 부분 문제를 해결하는 데는 상수 시간이면 충분하니 이 알고리즘의 시간 복잡도는 전체 이죠.
회고
Author And Source
이 문제에 관하여(문제 풀이 - 여행 짐 싸기(JAVA)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@qwe910205/문제-풀이-여행-짐-싸기JAVA
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
Author And Source
이 문제에 관하여(문제 풀이 - 여행 짐 싸기(JAVA)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@qwe910205/문제-풀이-여행-짐-싸기JAVA저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)