배낭 문제(Knapsack Problem)

배낭 문제(Knapsack Problem)는 조합 최적화의 유명한 문제로 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치(value)와 무게(weight)가 있는 N개의 짐(item)들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

 

그림. 배낭문제

[출처] https://en.wikipedia.org/wiki/Knapsack_problem

 

이 배낭문제는 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0 이상의 정수만 가능) 두 가지로 나눌 수 있는데,  짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem), 짐을 쪼갤 수 없는 경우의 배낭문제를 0-1 배낭문제(0-1 Knapsack Problem)라 부른다.

0-1 배낭문제(Knapsack problem)에서는 아이템을 쪼갤수 없기 때문에 아이템 1개를 가져가던지 버리던지 해야한다.

예를들어 짐들의 가치와 무게의 쌍(pairs)가 다음표와 같고 배낭의 최대 용량이 W = 50 이라고 할때 

짐(item)	무게(weight)	가치(value)
a	10	60
b	20	100
c	30	120

a=20 그리고 c= 30 kg 를 가져갈때 가치의 합이 220으로 최대가 될수 있다.

이 문제는 쪼갤 수 있는 경우에는 그리디 알고리즘으로 다항 시간에, 쪼갤 수 없는 경우에는 동적계획법(Dynamic Programming)등으로 의사 다항 시간에 풀 수 있다. [출처 : 위키백과-배낭문제]

 

반면 반면 쪼갤수 있는 배낭문제(Fractional Knapsack Problem)에서는 배낭의 총 가치를 극대화 할 수있도록 짐을 쪼갤수있다.

예를들어 위와 동일한 상황이라고 했을때 Fractional Knapsack Problem 에서는 최대 가치의 합이 240이 되는데 이유는 a=10kg, b=20kg 을 선텍하면 배낭에 담을 수 있는 나머지 무게는 50kg - 30kg = 20kg 이다.
나머지 c=30kg 이니 c의 2/3만 쪼개서 가져간다면 가치 = 60 + 100 + 120*(2/3) = 240이 되는것이다.

 

 

Fractional Kanpsack 문제 알고리즘

Fractional Knapsack Problem 문제를 해결하기위한 효율적인 방법은 Greedy 방식을 사용하는 것이다. 
1. 그리디 접근 방식의 기본 개념은 각 항목의  가치/무게의 비율을 계산하고이 비율을 기준으로 항목을 정렬한다
2. 가장 가치가 높은 비율 항목부터 가방에 담는다. 
가방에 담을때 현재 가방의 용량이 담을 항목의 무게보다 크다면 모두 선택하고 항목의 가치를 모두 더한다.
그렇지 않다면 현재 가방에 담을수 있는 용량 만큼 쪼개서 담고 가치는 비율만큼 계산하여 더해주고 루프를 바져나온다.

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
 
public class FractionalKnapsack {
 
 
 
    public static class Item {
        double weight;
        double value;
 
        public Item(double weight, double value) {
            this.weight = weight;
            this.value = value;
        }
 
        @Override
        public String toString() {
            return "Item{" +
                    "weight=" + weight +
                    ", value=" + value +
                    '}';
        }
    }
 
    public static void main(String[] args) {
 
        double capacity = 50;
 
        List<Item> items = Arrays.asList(
                new Item(10,60),
                new Item(40,40),
                new Item(20,100),
                new Item(30,120)
        );
        double maxValue = fractionalKnapsack(items, capacity);
        System.out.println("최대가치 합은 = " +
                maxValue);
 
    }
 
 
    public static double fractionalKnapsack(List<Item> items, double capacity) {
        //  항목의  가치/무게의 비율을 계산하고 비율을 기준으로 항목을 정렬한다.
        items = items.stream().sorted((a, b) -> {
            double aRatio = a.value/a.weight;
            double bRatio = b.value/b.weight ;
            if(aRatio > bRatio) return 1;
            else if(aRatio == bRatio) return 0 ;
            else return -1;
        }).collect(Collectors.toList());
 
        double totalValue = 0;
        double curCappacity = capacity;
        System.out.println(items);
        for(Item item : items) {
            // 현재 가방의 무게를 담을수 있는 상황이라면
            if(item.weight < curCappacity) {
                curCappacity -= item.weight;
                totalValue = item.value;
            }
            else { // 담을수 없는 상황이면 쪼개서 담아라.
                double fraction = ((double)capacity/(double)item.weight);
                totalValue += (item.value*fraction);
                break;
            }
        }
        return totalValue;
    }
 
}