15.2 분할 가능한 배낭 문제¶

문제

물건 \(n\) 개와 용량이 \(cap\)인 배낭이 주어진다. \(i\) 번째 물건의 무게는 \(wgt[i-1]\), 가치는 \(val[i-1]\)이다. 각 물건은 한 번만 선택할 수 있지만, 일부만 선택할 수 있으며 가치는 선택한 무게의 비율에 따라 계산한다. 용량 제한 안에서 배낭에 담을 수 있는 최대 가치를 구하라. 예시는 아래 그림(15-3)과 같다.

분할 가능한 배낭 문제 예시 데이터

그림 15-3 분할 가능한 배낭 문제 예시 데이터

분할 가능한 배낭 문제는 전체적으로 0-1 배낭 문제와 매우 비슷하다. 상태는 현재 물건 \(i\)와 용량 \(c\)를 포함하며, 목표는 용량 제한 안에서 최대 가치를 구하는 것이다.

차이점은 물건의 일부만 선택할 수 있다는 점이다. 아래 그림(15-4)과 같이 물건을 원하는 대로 나누고 무게 비율에 따라 그 가치를 계산할 수 있다.

물건 \(i\)의 단위 무게당 가치는 \(val[i-1] / wgt[i-1]\)이며, 줄여서 단위 가치라고 한다.
물건 \(i\)의 일부를 무게 \(w\)만큼 넣으면 배낭의 가치는 \(w \times val[i-1] / wgt[i-1]\)만큼 늘어난다.

물건의 단위 무게당 가치

그림 15-4 물건의 단위 무게당 가치

1. 탐욕 전략 결정¶

배낭 안의 총가치를 최대화하는 것은 본질적으로 단위 무게당 물건 가치를 최대화하는 것이다. 여기서 아래 그림(15-5)의 탐욕 전략을 도출할 수 있다.

물건을 단위 가치가 높은 순서로 정렬한다.
모든 물건을 순회하며 매번 단위 가치가 가장 높은 물건을 탐욕적으로 선택한다.
남은 용량이 부족하면 현재 물건의 일부로 배낭을 가득 채운다.

분할 가능한 배낭 문제의 탐욕 전략

그림 15-5 분할 가능한 배낭 문제의 탐욕 전략

2. 코드 구현¶

단위 가치순으로 정렬하기 쉽도록 물건 클래스 Item을 만든다. 탐욕적 선택을 반복하다가 배낭이 가득 차면 반복문을 빠져나와 해를 반환한다.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

fractional_knapsack.py

class Item:
    """물건"""

    def __init__(self, w: int, v: int):
        self.w = w  # 물건의 무게
        self.v = v  # 물건의 가치

def fractional_knapsack(wgt: list[int], val: list[int], cap: int) -> int:
    """분할 가능한 배낭: 탐욕"""
    # 무게와 가치 두 속성을 갖는 물건의 리스트를 생성한다
    items = [Item(w, v) for w, v in zip(wgt, val)]
    # 단위 가치 item.v / item.w를 기준으로 내림차순 정렬한다
    items.sort(key=lambda item: item.v / item.w, reverse=True)
    # 탐욕적 선택을 반복한다
    res = 0
    for item in items:
        if item.w <= cap:
            # 남은 용량이 충분하면 현재 물건을 통째로 배낭에 넣는다
            res += item.v
            cap -= item.w
        else:
            # 남은 용량이 부족하면 현재 물건의 일부를 배낭에 넣는다
            res += (item.v / item.w) * cap
            # 남은 용량이 없으므로 반복문을 종료한다
            break
    return res

fractional_knapsack.cpp

/* 물건 */
class Item {
  public:
    int w; // 물건의 무게
    int v; // 물건의 가치

    Item(int w, int v) : w(w), v(v) {
    }
};

/* 분할 가능한 배낭: 탐욕 */
double fractionalKnapsack(vector<int> &wgt, vector<int> &val, int cap) {
    // 무게와 가치 두 속성을 갖는 물건의 리스트를 생성한다
    vector<Item> items;
    for (int i = 0; i < wgt.size(); i++) {
        items.push_back(Item(wgt[i], val[i]));
    }
    // 단위 가치 item.v / item.w를 기준으로 내림차순 정렬한다
    sort(items.begin(), items.end(), [](Item &a, Item &b) { return (double)a.v / a.w > (double)b.v / b.w; });
    // 탐욕적 선택을 반복한다
    double res = 0;
    for (auto &item : items) {
        if (item.w <= cap) {
            // 남은 용량이 충분하면 현재 물건을 통째로 배낭에 넣는다
            res += item.v;
            cap -= item.w;
        } else {
            // 남은 용량이 부족하면 현재 물건의 일부를 배낭에 넣는다
            res += (double)item.v / item.w * cap;
            // 남은 용량이 없으므로 반복문을 종료한다
            break;
        }
    }
    return res;
}

fractional_knapsack.java

/* 물건 */
class Item {
    int w; // 물건의 무게
    int v; // 물건의 가치

    public Item(int w, int v) {
        this.w = w;
        this.v = v;
    }
}

/* 분할 가능한 배낭: 탐욕 */
double fractionalKnapsack(int[] wgt, int[] val, int cap) {
    // 무게와 가치 두 속성을 갖는 물건의 리스트를 생성한다
    Item[] items = new Item[wgt.length];
    for (int i = 0; i < wgt.length; i++) {
        items[i] = new Item(wgt[i], val[i]);
    }
    // 단위 가치 item.v / item.w를 기준으로 내림차순 정렬한다
    Arrays.sort(items, Comparator.comparingDouble(item -> -((double) item.v / item.w)));
    // 탐욕적 선택을 반복한다
    double res = 0;
    for (Item item : items) {
        if (item.w <= cap) {
            // 남은 용량이 충분하면 현재 물건을 통째로 배낭에 넣는다
            res += item.v;
            cap -= item.w;
        } else {
            // 남은 용량이 부족하면 현재 물건의 일부를 배낭에 넣는다
            res += (double) item.v / item.w * cap;
            // 남은 용량이 없으므로 반복문을 종료한다
            break;
        }
    }
    return res;
}

fractional_knapsack.cs

/* 물건 */
class Item(int w, int v) {
    public int w = w; // 물건의 무게
    public int v = v; // 물건의 가치
}

/* 분할 가능한 배낭: 탐욕 */
double FractionalKnapsack(int[] wgt, int[] val, int cap) {
    // 무게와 가치 두 속성을 갖는 물건의 리스트를 생성한다
    Item[] items = new Item[wgt.Length];
    for (int i = 0; i < wgt.Length; i++) {
        items[i] = new Item(wgt[i], val[i]);
    }
    // 단위 가치 item.v / item.w를 기준으로 내림차순 정렬한다
    Array.Sort(items, (x, y) => (y.v / y.w).CompareTo(x.v / x.w));
    // 탐욕적 선택을 반복한다
    double res = 0;
    foreach (Item item in items) {
        if (item.w <= cap) {
            // 남은 용량이 충분하면 현재 물건을 통째로 배낭에 넣는다
            res += item.v;
            cap -= item.w;
        } else {
            // 남은 용량이 부족하면 현재 물건의 일부를 배낭에 넣는다
            res += (double)item.v / item.w * cap;
            // 남은 용량이 없으므로 반복문을 종료한다
            break;
        }
    }
    return res;
}

fractional_knapsack.go

/* 물건 */
type Item struct {
    w int // 물건의 무게
    v int // 물건의 가치
}

/* 분할 가능한 배낭: 탐욕 */
func fractionalKnapsack(wgt []int, val []int, cap int) float64 {
    // 무게와 가치 두 속성을 갖는 물건의 리스트를 생성한다
    items := make([]Item, len(wgt))
    for i := 0; i < len(wgt); i++ {
        items[i] = Item{wgt[i], val[i]}
    }
    // 단위 가치 item.v / item.w를 기준으로 내림차순 정렬한다
    sort.Slice(items, func(i, j int) bool {
        return float64(items[i].v)/float64(items[i].w) > float64(items[j].v)/float64(items[j].w)
    })
    // 탐욕적 선택을 반복한다
    res := 0.0
    for _, item := range items {
        if item.w <= cap {
            // 남은 용량이 충분하면 현재 물건을 통째로 배낭에 넣는다
            res += float64(item.v)
            cap -= item.w
        } else {
            // 남은 용량이 부족하면 현재 물건의 일부를 배낭에 넣는다
            res += float64(item.v) / float64(item.w) * float64(cap)
            // 남은 용량이 없으므로 반복문을 종료한다
            break
        }
    }
    return res
}

fractional_knapsack.swift

/* 물건 */
class Item {
    var w: Int // 물건의 무게
    var v: Int // 물건의 가치

    init(w: Int, v: Int) {
        self.w = w
        self.v = v
    }
}

/* 분할 가능한 배낭: 탐욕 */
func fractionalKnapsack(wgt: [Int], val: [Int], cap: Int) -> Double {
    // 무게와 가치 두 속성을 갖는 물건의 리스트를 생성한다
    var items = zip(wgt, val).map { Item(w: $0, v: $1) }
    // 단위 가치 item.v / item.w를 기준으로 내림차순 정렬한다
    items.sort { -(Double($0.v) / Double($0.w)) < -(Double($1.v) / Double($1.w)) }
    // 탐욕적 선택을 반복한다
    var res = 0.0
    var cap = cap
    for item in items {
        if item.w <= cap {
            // 남은 용량이 충분하면 현재 물건을 통째로 배낭에 넣는다
            res += Double(item.v)
            cap -= item.w
        } else {
            // 남은 용량이 부족하면 현재 물건의 일부를 배낭에 넣는다
            res += Double(item.v) / Double(item.w) * Double(cap)
            // 남은 용량이 없으므로 반복문을 종료한다
            break
        }
    }
    return res
}

fractional_knapsack.js

/* 물건 */
class Item {
    constructor(w, v) {
        this.w = w; // 물건의 무게
        this.v = v; // 물건의 가치
    }
}

/* 분할 가능한 배낭: 탐욕 */
function fractionalKnapsack(wgt, val, cap) {
    // 무게와 가치 두 속성을 갖는 물건의 리스트를 생성한다
    const items = wgt.map((w, i) => new Item(w, val[i]));
    // 단위 가치 item.v / item.w를 기준으로 내림차순 정렬한다
    items.sort((a, b) => b.v / b.w - a.v / a.w);
    // 탐욕적 선택을 반복한다
    let res = 0;
    for (const item of items) {
        if (item.w <= cap) {
            // 남은 용량이 충분하면 현재 물건을 통째로 배낭에 넣는다
            res += item.v;
            cap -= item.w;
        } else {
            // 남은 용량이 부족하면 현재 물건의 일부를 배낭에 넣는다
            res += (item.v / item.w) * cap;
            // 남은 용량이 없으므로 반복문을 종료한다
            break;
        }
    }
    return res;
}

fractional_knapsack.ts

/* 물건 */
class Item {
    w: number; // 물건의 무게
    v: number; // 물건의 가치

    constructor(w: number, v: number) {
        this.w = w;
        this.v = v;
    }
}

/* 분할 가능한 배낭: 탐욕 */
function fractionalKnapsack(wgt: number[], val: number[], cap: number): number {
    // 무게와 가치 두 속성을 갖는 물건의 리스트를 생성한다
    const items: Item[] = wgt.map((w, i) => new Item(w, val[i]));
    // 단위 가치 item.v / item.w를 기준으로 내림차순 정렬한다
    items.sort((a, b) => b.v / b.w - a.v / a.w);
    // 탐욕적 선택을 반복한다
    let res = 0;
    for (const item of items) {
        if (item.w <= cap) {
            // 남은 용량이 충분하면 현재 물건을 통째로 배낭에 넣는다
            res += item.v;
            cap -= item.w;
        } else {
            // 남은 용량이 부족하면 현재 물건의 일부를 배낭에 넣는다
            res += (item.v / item.w) * cap;
            // 남은 용량이 없으므로 반복문을 종료한다
            break;
        }
    }
    return res;
}

fractional_knapsack.dart

/* 물건 */
class Item {
  int w; // 물건의 무게
  int v; // 물건의 가치

  Item(this.w, this.v);
}

/* 분할 가능한 배낭: 탐욕 */
double fractionalKnapsack(List<int> wgt, List<int> val, int cap) {
  // 무게와 가치 두 속성을 갖는 물건의 리스트를 생성한다
  List<Item> items = List.generate(wgt.length, (i) => Item(wgt[i], val[i]));
  // 단위 가치 item.v / item.w를 기준으로 내림차순 정렬한다
  items.sort((a, b) => (b.v / b.w).compareTo(a.v / a.w));
  // 탐욕적 선택을 반복한다
  double res = 0;
  for (Item item in items) {
    if (item.w <= cap) {
      // 남은 용량이 충분하면 현재 물건을 통째로 배낭에 넣는다
      res += item.v;
      cap -= item.w;
    } else {
      // 남은 용량이 부족하면 현재 물건의 일부를 배낭에 넣는다
      res += item.v / item.w * cap;
      // 남은 용량이 없으므로 반복문을 종료한다
      break;
    }
  }
  return res;
}

fractional_knapsack.rs

/* 물건 */
struct Item {
    w: i32, // 물건의 무게
    v: i32, // 물건의 가치
}

impl Item {
    fn new(w: i32, v: i32) -> Self {
        Self { w, v }
    }
}

/* 분할 가능한 배낭: 탐욕 */
fn fractional_knapsack(wgt: &[i32], val: &[i32], mut cap: i32) -> f64 {
    // 무게와 가치 두 속성을 갖는 물건의 리스트를 생성한다
    let mut items = wgt
        .iter()
        .zip(val.iter())
        .map(|(&w, &v)| Item::new(w, v))
        .collect::<Vec<Item>>();
    // 단위 가치 item.v / item.w를 기준으로 내림차순 정렬한다
    items.sort_by(|a, b| {
        (b.v as f64 / b.w as f64)
            .partial_cmp(&(a.v as f64 / a.w as f64))
            .unwrap()
    });
    // 탐욕적 선택을 반복한다
    let mut res = 0.0;
    for item in &items {
        if item.w <= cap {
            // 남은 용량이 충분하면 현재 물건을 통째로 배낭에 넣는다
            res += item.v as f64;
            cap -= item.w;
        } else {
            // 남은 용량이 부족하면 현재 물건의 일부를 배낭에 넣는다
            res += item.v as f64 / item.w as f64 * cap as f64;
            // 남은 용량이 없으므로 반복문을 종료한다
            break;
        }
    }
    res
}

fractional_knapsack.c

/* 물건 */
typedef struct {
    int w; // 물건의 무게
    int v; // 물건의 가치
} Item;

/* 분할 가능한 배낭: 탐욕 */
float fractionalKnapsack(int wgt[], int val[], int itemCount, int cap) {
    // 무게와 가치 두 속성을 갖는 물건의 리스트를 생성한다
    Item *items = malloc(sizeof(Item) * itemCount);
    for (int i = 0; i < itemCount; i++) {
        items[i] = (Item){.w = wgt[i], .v = val[i]};
    }
    // 단위 가치 item.v / item.w를 기준으로 내림차순 정렬한다
    qsort(items, (size_t)itemCount, sizeof(Item), sortByValueDensity);
    // 탐욕적 선택을 반복한다
    float res = 0.0;
    for (int i = 0; i < itemCount; i++) {
        if (items[i].w <= cap) {
            // 남은 용량이 충분하면 현재 물건을 통째로 배낭에 넣는다
            res += items[i].v;
            cap -= items[i].w;
        } else {
            // 남은 용량이 부족하면 현재 물건의 일부를 배낭에 넣는다
            res += (float)cap / items[i].w * items[i].v;
            cap = 0;
            break;
        }
    }
    free(items);
    return res;
}

fractional_knapsack.kt

/* 물건 */
class Item(
    val w: Int, // 물건
    val v: Int  // 물건의 가치
)

/* 분할 가능한 배낭: 탐욕 */
fun fractionalKnapsack(wgt: IntArray, _val: IntArray, c: Int): Double {
    // 무게와 가치 두 속성을 갖는 물건의 리스트를 생성한다
    var cap = c
    val items = arrayOfNulls<Item>(wgt.size)
    for (i in wgt.indices) {
        items[i] = Item(wgt[i], _val[i])
    }
    // 단위 가치 item.v / item.w를 기준으로 내림차순 정렬한다
    items.sortBy { item: Item? -> -(item!!.v.toDouble() / item.w) }
    // 탐욕적 선택을 반복한다
    var res = 0.0
    for (item in items) {
        if (item!!.w <= cap) {
            // 남은 용량이 충분하면 현재 물건을 통째로 배낭에 넣는다
            res += item.v
            cap -= item.w
        } else {
            // 남은 용량이 부족하면 현재 물건의 일부를 배낭에 넣는다
            res += item.v.toDouble() / item.w * cap
            // 남은 용량이 없으므로 반복문을 종료한다
            break
        }
    }
    return res
}

fractional_knapsack.rb

### 물건 ###
class Item
  attr_accessor :w # 물건의 무게
  attr_accessor :v # 물건의 가치

  def initialize(w, v)
    @w = w
    @v = v
  end
end

### 분할 가능한 배낭: 탐욕 ###
def fractional_knapsack(wgt, val, cap)
  # 무게와 가치 두 속성을 갖는 물건의 리스트를 생성한다
  items = wgt.each_with_index.map { |w, i| Item.new(w, val[i]) }
  # 단위 가치 item.v / item.w를 기준으로 내림차순 정렬한다
  items.sort! { |a, b| (b.v.to_f / b.w) <=> (a.v.to_f / a.w) }
  # 탐욕적 선택을 반복한다
  res = 0
  for item in items
    if item.w <= cap
      # 남은 용량이 충분하면 현재 물건을 통째로 배낭에 넣는다
      res += item.v
      cap -= item.w
    else
      # 남은 용량이 부족하면 현재 물건의 일부를 배낭에 넣는다
      res += (item.v.to_f / item.w) * cap
      # 남은 용량이 없으므로 반복문을 종료한다
      break
    end
  end
  res
end

코드 시각화

전체 화면 >

내장 정렬 알고리즘의 시간 복잡도는 보통 \(O(n \log n)\)이고, 공간 복잡도는 언어의 구체적인 구현에 따라 대체로 \(O(\log n)\) 또는 \(O(n)\)이다.

정렬을 제외하면 최악의 경우 물건 리스트 전체를 순회해야 하므로 시간 복잡도는 \(O(n)\)이다. 여기서 \(n\)은 물건 수다.

Item 객체 리스트를 초기화하므로 공간 복잡도는 \(O(n)\)이다.

3. 정확성 증명¶

귀류법을 사용하자. 물건 \(x\)의 단위 가치가 가장 높고, 어떤 알고리즘으로 구한 최대 가치가 res인데 그 해에 \(x\)가 없다고 가정한다.

배낭에서 임의의 물건을 단위 무게만큼 꺼내고 같은 무게의 물건 \(x\)로 바꾼다. \(x\)의 단위 가치가 가장 높으므로 바꾼 뒤의 총가치는 반드시 res보다 커진다. 이는 res가 최적해라는 가정에 모순이므로 최적해에는 물건 \(x\)가 포함되어야 한다.

그 해의 다른 물건에도 같은 모순을 구성할 수 있다. 즉, 단위 가치가 더 높은 물건이 항상 더 좋은 선택이며, 탐욕 전략이 유효함을 알 수 있다.

아래 그림(15-6)과 같이 물건 무게를 가로축, 단위 가치를 세로축으로 보면, 분할 가능한 배낭 문제는 '제한된 가로축 구간에서 최대 넓이를 구하는' 문제로 바뀐다. 이 비유는 탐욕 전략의 유효성을 기하학적으로 이해하는 데 도움이 된다.

분할 가능한 배낭 문제의 기하학적 표현

그림 15-6 분할 가능한 배낭 문제의 기하학적 표현

15.2 분할 가능한 배낭 문제¶

1. 탐욕 전략 결정¶

2. 코드 구현¶

3. 정확성 증명¶

댓글로 의견이나 질문, 제안을 남겨 주세요