728x90
반응형
SMALL
[알고리즘] Knapsack(배낭) 알고리즘 (그리디 및 dp) FKP KP 총정리
# Knapsack
# 냅색 알고리즘
# FKP
# KP
# 배낭문제
# 분할가능 배낭문제
# 0-1 배낭문제
# 다중 배낭문제
워낙 유명하디 유명해서리 컴공이라면 한번쯤은 들어봤을 녀석입니다.
바로 채득해보겠습니다.
1. Knapsack 알고리즘이란?
배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정한 가치의 무게가 정해진 짐들을 배낭에 담을 때, 가치의 합이 최대가 되는 조합을 찾는 알고리즘입니다.
대충 배낭에 비싼거 마구마구 담으라는 의미가 되겠습니다
대표적인 문제 유형에는 3가지가 있습니다.
- FKP : Fractional Knapsack Problem (분할가능 배낭 문제)
말 그대로 물건을 쪼갤 수 있는 배낭 문제입니다. 가치가 높은 순으로 정렬한 뒤 배낭에 담고, 텍스트남은 부분은 물건을 쪼개어 넣어 조합을 찾을 수 있을 수 있습니다. 물건이 배낭에 포함되거나 포함되지 않거나 두 가지 상태에 따라 그리디 알고리즘으로 해결 가능합니다. - KP : 0-1 Knapsack Problem (0-1 배낭 문제, 담거나 말거나라서 0-1)
물건을 쪼갤 수 없는 배낭 문제입니다. 아이템을 임의의 양으로 나눌 수 있어, 가치 대 무게 비율이 가장 높은 아이템부터 차례로 담아나감에 따라 동적계획법(Dynamic Programming) DP를 활용해 해결 가능합니다.
(보물 가치와 가방 여유공간이 정렬된 상황에서는 FKP와 동일하게 그리디로도 해결 가능합니다.) - MKP : Multiple Knapsack Problem (다중 배낭 문제)
배낭이 여러개인 문제입니다. 모든 사람의 배낭은 크기가 다를 수 있기 때문에, 모든 보물 조합을 탐색하는 DFS를 활용해 해결 가능합니다.
쪼개냐 마냐에 따라, 문제의 풀이 방법이 달라집니다.
FKP, KP, MKP 세가지 문제 모두 직접 풀어보겠습니다.
2. 그리디로 푸는 FKP (Fractional Kanpsack Problem)
가장 단순합니다. 앞서 말한 것 처럼 쪼갤 수 있는 문제 입니다.
무게10 가치10인 보물에 대해서, 무게3 가치3만큼만 쪼개서 담을 수 있습니다.
이렇게 쪼갤 수 있기에, 매 순간 최적해를 찾는 그리디 알고리즘을 활용하면 됩니다.
무게 당 이익 (= 이익 / 무게 ) 이 큰 순서대로 물건을 담으면 됩니다.
담다보면 배낭의 용량을 넘어서는 경우가 있는데, 이 때는 배낭의 남은 용량만큼만 짐을 넣으면 됩니다.
여기서 하나의 짐을 온전히 넣지 못하고 쪼개야하는 상황이 발생하기에 Fractional Knapsack Problem 으로 정의됩니다.
2.1 테스트 케이스
2 5 30
10 10
30 100
10 50
10 25
10 20
2.2 실행 결과
1952.3 설명
2명에게, 30짜리 배낭을 각각 지급했고, 5개의 보물들을 비싼것부터 담아야 하는 상황입니다.
단가를 기준으로 리스트를 내림차순 정렬 후
// 단가로 내림차순 정렬
Arrays.sort(goldList, (a,b) -> { // 단가 높은순 + 무게 무거운순
return Double.compare(b[2], a[2])==0 ? Double.compare(b[0], a[0]) : Double.compare(b[2], a[2]);
});// 무게, 가치, 단가 (단가순 내림차순 정렬)
10.0 50.0 5.0
30.0 100.0 3.3333333333333335
10.0 25.0 2.5
10.0 20.0 2.0
10.0 10.0 1.0
배낭이 넘치지 않을때까지 배낭에 담으면 됩니다.
보물의 크기가 잔여공간보다 크다면 쪼개서 꽉 채워 담으면 됩니다.
사용한 보물은 사용한 만큼 뺄셈 처리해줍니다.
for(int i=0; i<n; i++){ // 한명씩 보물을 담아보자
curBagSize = 0; // 배낭에 담긴 무게를 일단 초기화해주고
for(int j=0; j<k; j++){ // 보물들을 둘러보자
double weight = goldList[j][0];
if(weight <= 0){ // 사용완료 보물에 대한 처리
continue;
}
double value = goldList[j][1];
double perValue = goldList[j][2];
if(m-curBagSize > 0){ // 배낭에 빈 공간이 있는 경우
double canWeigh = Math.min( m-curBagSize, weight );
curBagSize += canWeigh; // 담을 수 있는 만큼 담고
dap += canWeigh * perValue; // 가치 더해주고
goldList[j][0] -= canWeigh; // 해당 보물 사용처리
}
if(curBagSize == m){ // 배낭이 꽉찼으면 조기종료
break;
}
}
}
결과적으로 (10, 10)인 보물을 제외한 보물들을 모두 더하면 195 를 구할 수 있습니다.
195
추가적으로, 나눗셈 연산에서 실수 자료형인 double을 사용했습니다.
Float을 사용하지 않고 Double을 사용한 이유는 다음과 같습니다.
- 정밀도: Float은 32비트로 표현되고, double은 64비트로 표현됩니다. 따라서 double은 훨씬 더 많은 유효 자릿수를 제공해 정밀한 계산이 가능합니다. 알고리즘 문제에서는 부동소수점 연산의 정밀도가 중요한 경우가 많기 때문에 double을 선호하게 됩니다.
- 안정성: Double은 더 높은 정밀도 덕분에 오차가 적고, 특히 반복 계산이나 매우 작은 차이를 다루는 알고리즘에서는 float보다 안정적인 결과를 제공합니다.
- 범위: Double은 더 넓은 표현 범위를 가지고 있습니다. 아주 큰 수나 아주 작은 수를 다룰 때 overflow나 underflow 문제가 발생할 확률이 낮습니다.
- 기본 자료형 사용: 대부분의 컴파일러와 라이브러리는 부동소수점 연산 시 double을 기본으로 사용합니다. 이는 호환성과 연산의 일관성을 높여주며, 따로 float으로 형 변환하지 않아도 됩니다.
반올림, 올림, 내림의 조건은 문제에 맞춰 자유자재로 구현하면 되겠습니다.
2.4 전체 코드
import java.io.*;
import java.util.*;
public class Main {
public static double dap = 0;
public static int n, k, m;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// Knapsack(배낭) 알고리즘 - 그리디
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken()); // 인원수
k = Integer.parseInt(st.nextToken()); // 보물 개수
m = Integer.parseInt(st.nextToken()); // 배낭 크기
Double goldList[][] = new Double[k][3]; // 보물(무게, 가치, 단가)
for(int i=0; i<k; i++){
st = new StringTokenizer(br.readLine());
goldList[i][0] = Double.parseDouble(st.nextToken());
goldList[i][1] = Double.parseDouble(st.nextToken());
goldList[i][2] = goldList[i][1]/goldList[i][0];
}
// 단가로 내림차순 정렬
// Arrays.sort(goldList, (a,b) -> (int) (a[2]==b[2] ? b[0]-a[0] : b[2]-a[2])); // int로 정렬시 정밀도 손실 발생
Arrays.sort(goldList, (a,b) -> { // 단가 높은순 + 무게 무거운순
return Double.compare(b[2], a[2])==0 ? Double.compare(b[0], a[0]) : Double.compare(b[2], a[2]);
});
/*
for(int i=0; i<k; i++){
for(int j=0; j<3; j++){
System.out.print(goldList[i][j] + " ");
}
System.out.println();
}
*/
int curBagSize = 0;
for(int i=0; i<n; i++){ // 한명씩 보물을 담아보자
curBagSize = 0; // 배낭에 담긴 무게를 일단 초기화해주고
for(int j=0; j<k; j++){ // 보물들을 둘러보자
double weight = goldList[j][0];
if(weight <= 0){ // 사용완료 보물에 대한 처리
continue;
}
double value = goldList[j][1];
double perValue = goldList[j][2];
if(m-curBagSize > 0){ // 배낭에 빈 공간이 있는 경우
double canWeigh = Math.min( m-curBagSize, weight );
curBagSize += canWeigh; // 담을 수 있는 만큼 담고
dap += canWeigh * perValue; // 가치 더해주고
goldList[j][0] -= canWeigh; // 해당 보물 사용처리
}
if(curBagSize == m){ // 배낭이 꽉찼으면 조기종료
break;
}
}
}
// dap = (int) (Math.round(dap * 100) / 100.0);
bw.write(String.valueOf(dap) + "\n");
bw.flush();
bw.close();
}
}
3. 그리디로 푸는 KP (0-1 Knapsack Problem)
보물을 쪼갤 수 없음에도 불구하고
아래의 두가지 특정 조건을 만족하면 그리디로도 풀이가 가능합니다.
- 보물 가치 기반 정렬:
- 보물들을 가치가 높은 순서대로 정렬한 다음, 가방에 담는 방식입니다.
- 각 보물을 가장 높은 가치를 가진 보물부터 차례로 가방에 담습니다.
- 가방의 여유 공간 기반 정렬:
- 각 가방의 여유 공간이 큰 순서대로 정렬한 다음, 보물을 넣습니다.
- 이 방법은 공간의 여유를 고려하여 보물을 담는 방식입니다.
3.1 테스트 케이스와 실행 결과
위와 동일합니다.
3.2 설명
보물의 가치(=무게당 가치)를 기준으로 정렬하고, 각 가방에 보물을 넣는 그리디 접근 방식입니다.
쪼개지 않고 통째로 담을 수 있는지 체크해서, 보물 하나를 통째로 처리했습니다.
3.3 전체코드
import java.io.*;
import java.util.*;
public class Main {
public static double dap = 0;
public static int n, k, m;
public static Integer[][] goldList;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 0-1 KP : 0-1 Knapsack Problem (0-1 배낭 문제, 담거나 말거나라서 0-1)
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken()); // 인원수
k = Integer.parseInt(st.nextToken()); // 보물 개수
m = Integer.parseInt(st.nextToken()); // 가방 크기
Double goldList[][] = new Double[k][3]; // 보물(무게, 가치, 단가)
for(int i=0; i<k; i++){
st = new StringTokenizer(br.readLine());
goldList[i][0] = Double.parseDouble(st.nextToken());
goldList[i][1] = Double.parseDouble(st.nextToken());
goldList[i][2] = goldList[i][1]/goldList[i][0];
}
// 단가로 내림차순 정렬
Arrays.sort(goldList, (a,b) -> { // 단가 높은순 + 무게 무거운순
return Double.compare(b[2], a[2])==0 ? Double.compare(b[0], a[0]) : Double.compare(b[2], a[2]);
});
int curBagSize = 0;
for(int i=0; i<n; i++){ // 한명씩 보물을 담아보자
curBagSize = 0; // 배낭에 담긴 무게를 일단 초기화해주고
for(int j=0; j<k; j++){ // 보물들을 둘러보자
double weight = goldList[j][0];
if(weight <= 0){ // 사용완료 보물에 대한 처리
continue;
}
double value = goldList[j][1];
if(m-curBagSize >= weight){ // 배낭에 빈 공간이 > 보물보다 크면, 담을 수 있으니
curBagSize += weight; // 해당 보물 통째로 담고
dap += value; // 해당 보물 통째로 가치 더해주고
goldList[j][0] -= weight; // 해당 보물 통째로 사용처리
}
if(curBagSize == m){ // 배낭이 꽉찼으면 조기종료
break;
}
}
}
bw.write(String.valueOf(dap) + "\n");
bw.flush();
bw.close();
}
}
4. DFS로 푸는 MKP (Multiple Kanpsack Problem)
앞서 말한 것 처럼 배낭이 여러개입니다.
우연히 무게 제한이 A인 배낭에 담긴 물건이, 무게 제한이 B인 배낭에 담길 때 가치가 최대일 수도 있기에
DFS를 통해 모든 보물 조합을 탐색해야 합니다. (본 풀이에서는 모든 배낭 크기 동일)
4.1 테스트 케이스와 실행 결과
위와 동일합니다.
4.2 설명
모든 보물에 대해서, 모든 사람들이, 각자 본인의 배낭에 담을 수 있는, 모든 경우의 수를 따져봅니다.
- DFS 탐색:
- 현재 보물을 사용하는 경우와 사용하지 않는 경우를 모두 탐색합니다.
- used 배열을 사용하여 보물의 사용 여부를 추적합니다. 보물이 사용되면 다른 사람에게는 사용할 수 없습니다.
- bagCapacity 배열을 사용하여 각 사람의 가방 용량을 업데이트합니다.
- 백트래킹을 통해 탐색이 끝난 후 보물의 사용 상태와 가방 용량을 원래 상태로 되돌립니다.
- 최대 가치 계산: 모든 가능한 보물 조합을 탐색한 후 최대 가치를 업데이트합니다.
4.3 전체코드
import java.io.*;
import java.util.*;
public class Main {
public static int dap = 0;
public static int n, k, m;
public static Integer[][] goldList;
public static boolean[] used;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 0-1 MKP : 0-1 Multiple Knapsack Problem (0-1 다중 배낭 문제, 담거나 말거나라서 0-1)
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken()); // 인원수
k = Integer.parseInt(st.nextToken()); // 보물 개수
m = Integer.parseInt(st.nextToken()); // 가방 크기
goldList = new Integer[k][2]; // 보물(무게, 가치)
used = new boolean[k]; // 보물 사용 여부 배열
for(int i=0; i<k; i++) {
st = new StringTokenizer(br.readLine());
goldList[i][0] = Integer.parseInt(st.nextToken());
goldList[i][1] = Integer.parseInt(st.nextToken());
used[i] = false;
}
// DFS를 통해 모든 보물 조합 탐색
int goldIndex = 0;
int[] bagCapacity = new int[n];
dfs(goldIndex, bagCapacity, 0);
bw.write(String.valueOf(dap) + "\n");
bw.flush();
bw.close();
}
// DFS 탐색 함수
public static void dfs(int goldIndex, int[] bagCapacity, int sum) {
// 모든 보물에 대해 탐색 완료한 경우
if (goldIndex==k) {
// 모든 신입사원의 가방에 담긴 보물의 총 가치를 계산
dap = Math.max(dap, sum);
return;
}
// 현재(goldIndex번째) 보물을 사용할 경우, 각 사람마다 goldWeight를 더해줘보며 최대값을 찾는다.
for (int person=0; person<n; person++) {
int goldWeight = goldList[goldIndex][0];
int goldValue = goldList[goldIndex][1];
int tobeWeight = bagCapacity[person]+goldWeight;
if (!used[goldIndex] && tobeWeight <= m) { // 미사용 && 배낭무게를 넘지않는다면
used[goldIndex] = true; // 보물 사용처리
bagCapacity[person] += goldWeight; // 현재 신입사원의 가방 용량 업데이트
dfs(goldIndex+1, bagCapacity, sum+goldValue); // 다음 보물로 이동
bagCapacity[person] -= goldWeight; // 백트래킹: 현재 신입사원의 가방 용량 되돌리기
used[goldIndex] = false; // 백트래킹: 보물 사용 상태 되돌리기
}
}
// 현재(goldIndex번째) 보물을 사용하지 않는 경우, 아무 처리하지 않고 그냥 다음 보물로 이동한다.
dfs(goldIndex+1, bagCapacity, sum);
}
}
MKP 참고하기 좋은 링크
https://deepdata.tistory.com/1285
가방이 여러개인 multiple 0-1 knapsack(배낭 문제) 해법 배우기
1. 다중 배낭 문제(multiple 0-1 knapsack) https://atcoder.jp/contests/past202206-open/tasks/past202206_h H - Two KnapsacksAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.
deepdata.tistory.com
728x90
반응형
LIST
'알고리즘 단련장 > 준비운동' 카테고리의 다른 글
| [알고리즘] 자바 소수점 원하는 자리수 만큼 반올림 올림 버림 출력 (String.format, Math) (0) | 2024.08.01 |
|---|