배낭 문제

배낭 문제는 무게 한도 안에서 값의 합이 가장 커지도록 담을 물건을 고르는 계산 문제입니다. 물건 목록과 한도를 넣으면 어떤 물건을 담을지가 답으로 나옵니다. 물건이 늘수록 따져 볼 조합이 두 배씩 불어나 풀기 어려워집니다. 한정된 자원을 나눠 쓰는 여러 문제가 이 꼴입니다.

상세

배낭 문제(knapsack problem)는 조합 최적화 문제의 하나입니다. 조합 최적화는 가능한 조합 가운데 목표로 삼은 값이 가장 크거나 가장 작은 하나를 찾는 문제를 말합니다. 짐을 꾸릴 때 무엇을 넣고 무엇을 두고 갈지 고르는 장면을 떠올리면 됩니다.

이 절은 물건 셋과 한도 5 짜리 작은 예 하나로 끝까지 갑니다. 먼저 후보를 전부 보는 풀이와 욕심껏 고르는 풀이가 각각 어디서 막히는지 봅니다. 물건을 쪼갤 수 있으면 욕심껏 고르는 풀이가 왜 맞는지도 이때 봅니다.

다음으로 표를 채우는 풀이로 답을 얻고 그 비용을 셉니다. 이어서 이 문제가 얼마나 어려운지와 변형을 봅니다. 끝으로 입력 크기에 따라 풀이를 고르는 방법으로 마칩니다.

입력과 출력

입력은 물건 n 개와 가방의 무게 한도 W 입니다. 물건 i 마다 무게 wᵢ 와 값 vᵢ 가 붙어 있습니다. 출력은 담을 물건의 묶음입니다.

묶음에는 조건이 하나 있습니다. 담은 물건의 무게 합이 W 를 넘으면 안 됩니다. 이 조건을 지키는 묶음 가운데 값의 합이 가장 큰 것이 답입니다.

물건은 통째로 넣거나 빼야 합니다. 반만 넣을 수는 없습니다. 물건마다 0(뺀다)이나 1(넣는다)을 고르는 셈이라 이 꼴을 0-1 배낭 문제라고 부릅니다. 그냥 배낭 문제라고 하면 대개 이것을 가리킵니다.

이 절 내내 쓸 예는 아래와 같습니다. 가방의 한도는 5 입니다.

답은 나와 다를 담는 것입니다. 무게 합이 5 로 한도에 꼭 맞고 값의 합은 22 입니다.

후보를 전부 보는 풀이

가장 곧은 풀이는 완전 탐색입니다. 답이 될 수 있는 후보를 하나도 빼지 않고 전부 확인하는 방식입니다. 배낭 문제의 후보는 물건 묶음입니다. 물건마다 넣을지 뺄지 정한 묶음을 부분집합이라고 부릅니다.

물건이 셋이면 부분집합은 8 개입니다. 아래 표는 8 개를 모두 늘어놓고 무게 합과 값의 합을 적은 것입니다.

셋을 다 담으면 값이 28 로 가장 크지만 무게가 6 이라 한도를 넘습니다. 한도 안인 일곱 가운데 값이 가장 큰 것은 「나 다」의 22 입니다.

이 풀이는 물건이 늘면 금세 막힙니다. 물건마다 넣거나 빼는 두 갈래가 있어서 물건이 하나 늘 때마다 후보가 두 배가 됩니다. 물건이 n 개면 후보는 2ⁿ 개입니다.

아래 그림은 물건을 하나씩 정해 내려가며 갈래가 나뉘는 모양입니다. 한 층 내려갈 때마다 갈래가 두 배가 됩니다. 맨 아래 여덟 묶음이 앞 표의 여덟 줄입니다.

flowchart TD
    S["아직 아무것도 안 정했다"]
    subgraph 층1["가를 정한다 · 2 갈래"]
        A1["가 넣음"]
        A0["가 뺌"]
    end
    subgraph 층2["나를 정한다 · 4 갈래"]
        B11["나 넣음"]
        B10["나 뺌"]
        B01["나 넣음"]
        B00["나 뺌"]
    end
    subgraph 층3["다를 정한다 · 8 묶음"]
        C111["가 나 다 · 무게 6 · 한도 초과"]
        C110["가 나"]
        C101["가 다"]
        C100["가"]
        C011["나 다"]
        C010["나"]
        C001["다"]
        C000["빈 묶음"]
    end
    S --> A1
    S --> A0
    A1 --> B11
    A1 --> B10
    A0 --> B01
    A0 --> B00
    B11 --> C111
    B11 --> C110
    B10 --> C101
    B10 --> C100
    B01 --> C011
    B01 --> C010
    B00 --> C001
    B00 --> C000

물건이 30 개면 후보가 10억 개를 넘습니다. 2³⁰ 이 1,073,741,824 입니다. 입력이 조금 늘 때 후보가 이렇게 불어나는 현상을 조합 폭발이라고 합니다.

입력이 커질 때 일이 느는 빠르기는 O(…) 꼴로 적습니다. 이 표기를 빅오 표기법이라고 합니다. n 이 커질 때 일이 n 에 비례하면 O(n), n² 에 비례하면 O(n²) 입니다.

이 풀이는 후보 2ⁿ 개마다 물건 n 개의 무게와 값을 더해 봅니다. 드는 일은 O(n·2ⁿ) 입니다. 물건이 하나 늘면 일이 두 배 넘게 늡니다.

욕심껏 고르면 놓치는 답

후보를 다 보지 않고 좋아 보이는 것부터 담으면 어떨까요. 매 단계에서 지금 가장 좋아 보이는 하나만 고르는 방식을 그리디 알고리즘이라고 합니다. 배낭 문제에서 자연스러운 기준은 무게 1 당 값입니다.

예의 물건은 무게 1 당 값이 가는 6, 나는 5, 다는 4 입니다. 그래서 가부터 담습니다. 다음으로 나를 담으면 무게 3, 값 16 이 됩니다.

남은 한도는 2 입니다. 다는 무게가 3 이라 들어가지 않습니다. 그리디는 여기서 값 16 으로 끝납니다. 답인 22 보다 작습니다.

놓친 까닭은 고른 것을 되돌리지 않기 때문입니다. 가를 먼저 담은 탓에 다가 들어갈 공간이 모자라졌습니다. 가를 빼고 나와 다를 담는 편이 나았지만 그리디는 그 갈래를 보지 않습니다.

지금 가장 좋아 보이는 선택이 전체 답에도 들어 있다는 성질을 탐욕 선택 속성이라고 합니다. 이 성질이 있어야 그리디가 언제나 맞는 답을 냅니다. 0-1 배낭 문제에는 이 성질이 없습니다.

쪼갤 수 있는 배낭

물건을 쪼개 담을 수 있으면 사정이 달라집니다. 쌀이나 기름처럼 원하는 만큼만 덜어 담을 수 있다고 칩시다. 이 꼴을 분할 가능 배낭 문제(fractional knapsack problem)라고 부릅니다.

이때는 무게 1 당 값이 큰 것부터 담는 그리디가 언제나 최적의 답을 냅니다. 가와 나를 통째로 담으면 무게 3, 값 16 입니다. 남은 한도 2 에는 다를 3 분의 2 만 덜어 담습니다. 다의 값 12 의 3 분의 2 인 8 이 더해져 값은 24 가 됩니다.

쪼갤 수 있으면 공간이 남지 않습니다. 그래서 무게 1 당 값이 가장 큰 것부터 채우면 그보다 값을 더 얻을 방법이 없습니다.

아래 그림은 한도 5 를 칸 다섯으로 놓고 세 경우에 무엇이 칸을 채우는지 그린 것입니다. 칸 하나가 무게 1 입니다. 0-1 에서 그리디는 두 칸을 비웁니다. 쪼갤 수 있으면 빈칸이 생기지 않습니다.

block-beta
columns 5
  t1["0-1 · 그리디로 고름 · 값 16"]:5
  a1["가"] a2["나"]:2 a3["빈 공간"]:2
  t2["0-1 · 나와 다 · 값 22"]:5
  b1["나"]:2 b2["다"]:3
  t3["쪼개 담기 · 값 24"]:5
  c1["가"] c2["나"]:2 c3["다의 ⅔"]:2

이 그리디는 물건을 무게 1 당 값 순으로 정렬하는 데 드는 일이 대부분이라 O(n log n) 입니다. 물건 수 n 에 그 로그를 곱한 만큼 늘어난다는 뜻입니다.

이 24 는 0-1 배낭의 답 22 보다 큽니다. 쪼갤 수 있는 쪽이 늘 더 자유롭기 때문입니다. 그래서 쪼갤 수 있다고 친 답은 0-1 답이 넘을 수 없는 위쪽 한계가 됩니다.

분기 한정은 이 한계를 써서 후보를 덜 봅니다. 후보를 넣기와 빼기 갈래로 나눠 내려갑니다. 갈래마다 남은 물건을 쪼갤 수 있다고 치고 위쪽 한계를 셉니다. 그 한계가 지금까지 찾은 가장 큰 값보다 작으면 그 갈래 아래는 보지 않습니다.

표를 채우는 풀이

0-1 배낭 문제를 빠르게 푸는 대표 방법은 동적 계획법입니다. 큰 문제를 작은 문제로 나눈 뒤 작은 문제의 답을 표에 적어 두고 다시 쓰는 방식입니다. 같은 계산을 두 번 하지 않으므로 완전 탐색보다 훨씬 적게 일합니다.

배낭 문제에서 작은 문제는 이렇게 잡습니다. 앞의 물건 i 개만 쓸 수 있고 한도가 c 일 때 얻을 수 있는 가장 큰 값입니다. 이 값을 표의 칸 (i, c) 에 적습니다. 표는 쓸 수 있는 물건 수 i 를 행으로, 한도 c 를 열로 놓습니다. 구하려는 답은 물건을 다 쓰고 한도가 W 인 칸 (n, W) 입니다.

칸 (i, c) 를 채울 때는 물건 i 하나만 놓고 넣을지 뺄지를 봅니다. 앞의 i−1 개를 어떻게 담을지는 이미 위 행이 답해 두었습니다.

• 뺀다. 물건 i 없이 앞 i−1 개로 한도 c 를 채웁니다. 값은 칸 (i−1, c) 입니다
• 넣는다. 물건 i 의 무게가 c 이하일 때만 고를 수 있습니다. 물건 i 가 무게 wᵢ 를 차지하므로 앞 i−1 개에는 한도 c−wᵢ 가 남습니다. 값은 칸 (i−1, c−wᵢ) 에 vᵢ 를 더한 것입니다

두 값 가운데 큰 쪽이 칸 (i, c) 의 값입니다. 이처럼 한 값을 더 작은 문제의 값으로 적는 식을 점화식이라고 합니다.

아래 그림은 칸 하나가 어느 칸을 보는지를 그린 것입니다. 두 칸 모두 한 행 위에 있습니다. 「뺀다」의 칸은 바로 위입니다. 「넣는다」의 칸은 거기서 wᵢ 칸만큼 왼쪽입니다.

flowchart TD
    subgraph 위행["위 행 · 앞 i−1 개만 쓴다"]
        P1["칸 (i−1, c−wᵢ) · wᵢ 칸 왼쪽"]
        P2["칸 (i−1, c) · 바로 위"]
    end
    subgraph 이행["이 행 · 앞 i 개를 쓴다"]
        X["칸 (i, c) · 두 값 가운데 큰 쪽"]
    end
    P1 -->|"넣는다 · vᵢ 를 더한다"| X
    P2 -->|"뺀다"| X

그래서 표를 맨 위 행부터 한 행씩 채우면 됩니다. 칸 하나를 채울 때 보는 두 칸은 언제나 이미 채워져 있습니다. 맨 위 행은 물건을 하나도 안 쓰는 경우라 모든 칸이 0 입니다.

예로 채운 표

아래 표는 예의 물건 셋으로 칸을 다 채운 결과입니다. 행은 쓸 수 있는 물건입니다. 맨 윗줄의 0 부터 5 까지는 한도 c 입니다.

맨 아래 오른쪽 칸 22 가 답입니다. 이 칸이 어떻게 나왔는지 따라가 봅니다. 다를 빼면 바로 위 칸의 16 입니다. 다를 넣으면 다의 무게 3 을 뺀 한도 2 의 위 칸 10 에 다의 값 12 를 더해 22 입니다. 22 가 더 커서 22 를 적습니다.

한도 3 의 칸은 결과가 반대입니다. 다를 빼면 위 칸의 16 입니다. 다를 넣으면 한도 0 의 위 칸 0 에 12 를 더해 12 입니다. 16 이 더 커서 한도가 3 이면 다를 안 담는 편이 낫습니다.

표에서 어떤 물건을 담았는지도 읽어 낼 수 있습니다. 답 칸에서 출발해 바로 위 칸과 값을 견줍니다. 값이 다르면 그 행의 물건을 넣은 것입니다.

넣었으면 한 행 올라가면서 그 물건의 무게만큼 왼쪽으로 옮깁니다. 한도에서 그 무게를 뺀 열로 간다는 뜻입니다. 값이 같으면 열은 그대로 두고 한 행만 올라갑니다.

예에서는 이렇게 거슬러 올라갑니다.

1. 칸 (다까지, 5) 의 22 는 위 칸 16 과 다릅니다. 다를 넣었습니다. 한도 5 에서 다의 무게 3 을 빼 칸 (나까지, 2) 로 갑니다
2. 칸 (나까지, 2) 의 10 은 위 칸 6 과 다릅니다. 나도 넣었습니다. 한도 2 에서 나의 무게 2 를 빼 칸 (가까지, 0) 으로 갑니다
3. 칸 (가까지, 0) 의 0 은 위 칸 0 과 같습니다. 가는 안 넣었습니다

담은 물건은 나와 다입니다.

파이썬으로 옮긴 풀이

아래 함수는 앞 소절의 표를 파이썬으로 채웁니다. items 는 (무게, 값) 짝의 목록입니다. limit 는 가방의 한도입니다. 돌려주는 값은 얻을 수 있는 가장 큰 값의 합입니다.

def knapsack(items, limit):
    n = len(items)
    dp = [[0] * (limit + 1)
          for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = items[i - 1]
        for c in range(limit + 1):
            dp[i][c] = dp[i - 1][c]
            if w <= c:
                take = dp[i - 1][c - w] + v
                dp[i][c] = max(dp[i][c], take)
    return dp[n][limit]

items = [(1, 6), (2, 10), (3, 12)]
knapsack(items, 5)  # 22
knapsack(items, 3)  # 16
knapsack(items, 0)  # 0

dp 가 앞 소절의 표입니다. 행은 n+1 개입니다. 열은 limit+1 개입니다. 처음에는 모든 칸이 0 이라 맨 위 행이 저절로 채워져 있습니다.

바깥 반복문이 물건을 하나씩 고릅니다. 안쪽 반복문은 한도를 0 부터 늘립니다. 칸마다 먼저 「뺀다」의 값을 적습니다. 물건이 들어갈 만하면 「넣는다」의 값과 견줘 큰 쪽으로 바꿉니다.

코드 끝의 세 줄은 같은 물건 목록에 한도만 바꿔 부른 것입니다. 한도 5 와 3 의 결과는 앞 표의 마지막 행에 있는 값과 같습니다. 한도가 0 이면 아무것도 못 담아 0 입니다.

걸리는 시간과 메모리

표의 칸은 (n+1)(W+1) 개입니다. 칸 하나에 드는 일은 두 값을 견주는 것뿐이라 시간은 O(nW) 입니다.

표를 통째로 들고 있으면 메모리도 O(nW) 가 듭니다. 그런데 칸을 채울 때는 바로 위 행만 봅니다. 그래서 행 하나만 남겨 두고 덮어쓰면 메모리를 O(W) 로 줄일 수 있습니다.

행 하나로 줄이면 칸 c 가 보던 위 행의 칸 c−wᵢ 는 같은 줄의 왼쪽 칸이 됩니다. 이 줄은 지금 물건을 넣어 보며 덮어쓰는 중입니다. 그래서 한도를 큰 쪽부터 거꾸로 채웁니다.

예의 물건 가(무게 1, 값 6)로 칸 0~2 만 채워 봅니다. 처음에는 모든 칸이 0 입니다. 아래 그림은 작은 쪽부터 채울 때와 큰 쪽부터 채울 때를 위아래로 견줍니다.

flowchart TD
    subgraph 작은쪽["① 작은 쪽부터 · 칸 1 → 칸 2"]
        A1["칸 1 · 칸 0 의 0 + 6 = 6 으로 덮어쓴다"]
        A2["칸 2 · 6 + 6 = 12 · 가를 두 번 넣었다"]
        A1 -->|"칸 2 가 덮어쓴 칸 1 을 읽는다"| A2
    end
    subgraph 큰쪽["② 큰 쪽부터 · 칸 2 → 칸 1"]
        B1["칸 1 · 아직 0"]
        B2["칸 2 · 0 + 6 = 6 으로 덮어쓴다"]
        B3["칸 1 · 칸 0 의 0 + 6 = 6 으로 덮어쓴다"]
        B1 -->|"칸 2 가 읽는다"| B2
        B2 -->|"그다음 차례"| B3
    end
    A2 ~~~ B1

작은 쪽부터 채우면 칸 1 이 먼저 6 으로 바뀝니다. 칸 2 는 바뀐 칸 1 을 읽어 12 를 적습니다. 가는 하나뿐입니다. 그런데 두 번 넣은 값이 섞였습니다.

큰 쪽부터 채우면 칸 2 가 아직 0 인 칸 1 을 읽어 6 을 적습니다. 그다음에 칸 1 이 바뀝니다. 두 칸 모두 가를 한 번만 넣은 값입니다.

행 하나만 남기면 잃는 것도 있습니다. 위 행들을 지웠으니 「예로 채운 표」처럼 어떤 물건을 담았는지 거슬러 읽어 낼 수 없습니다.

무게는 정수여야 합니다. 한도 c 가 표의 열 번호이기 때문입니다. 무게가 0.37 처럼 소수이면 단위를 바꿔 정수로 만듭니다. 그만큼 W 도 커져 표가 커집니다.

의사 다항 시간

풀이에 드는 시간은 입력 크기에 견줘 잽니다. 입력 크기는 입력을 적는 데 드는 글자 수입니다. n² 이나 n³ 처럼 입력 크기의 거듭제곱으로 적히는 시간을 다항 시간이라고 합니다. 입력이 커져도 감당할 만하게 늘어나는 시간입니다.

O(nW) 도 얼핏 다항 시간처럼 보입니다. 그런데 n 과 W 는 입력 크기에 들어가는 방식이 다릅니다.

n 은 물건의 개수입니다. 물건이 하나 늘면 적을 글자도 물건 하나만큼 늡니다. W 는 수의 크기입니다. W 를 적는 데 드는 글자는 W 의 자릿수뿐입니다.

한도가 1,000 이면 네 자리입니다. 한도가 1,000,000,000 이면 열 자리입니다. 입력 크기는 여섯 자리 늘었을 뿐입니다. 그런데 표의 열은 백만 배가 됩니다.

입력 크기로 재면 이 풀이의 시간은 자릿수가 하나 늘 때마다 열 배씩 불어납니다. W 의 값으로 재면 다항식처럼 보여도 입력 크기로 재면 다항식이 아닙니다. 이런 시간을 의사 다항 시간(pseudo-polynomial time)이라고 부릅니다.

그래서 이 풀이는 한도가 작은 정수일 때 잘 듣습니다. 물건이 수천 개여도 한도가 수만 정도면 표를 다 채울 만합니다. 한도가 커지면 표를 채우는 일이 감당 못 할 만큼 커집니다.

얼마나 어려운 문제인가

배낭 문제를 「예」나 「아니오」로 답하는 꼴로 바꿀 수 있습니다. 「무게 합이 W 이하이면서 값의 합이 V 이상인 묶음이 있나」를 묻는 것입니다. 이렇게 예나 아니오로 답하는 문제를 결정 문제라고 부릅니다.

NP(Nondeterministic Polynomial time, 비결정적 다항 시간)는 답이 주어지면 맞는지를 다항 시간에 확인할 수 있는 결정 문제의 모임입니다. 배낭 문제의 결정 문제도 여기 듭니다. 묶음을 하나 받으면 무게와 값을 더해 보는 것으로 금방 확인되기 때문입니다.

이름의 「비결정적」은 맞는 답을 알아서 골라 주는 가상의 기계를 가리킵니다. 그런 기계가 있으면 남는 일은 고른 답을 확인하는 것뿐입니다. 그래서 앞의 정의와 같은 말이 됩니다.

NP 안에서 가장 어려운 쪽에 드는 문제를 NP-완전이라고 부릅니다. 이 가운데 하나라도 모든 입력에서 다항 시간에 푸는 방법이 나오면 NP 의 모든 문제가 다항 시간에 풀립니다.

P(Polynomial time, 다항 시간)는 다항 시간에 풀 수 있는 결정 문제의 모임입니다. P 의 문제는 답을 확인하는 것도 다항 시간이라 모두 NP 에 듭니다. 거꾸로 NP 의 모든 문제가 P 에 드는지는 아직 아무도 모릅니다. 이 물음이 P 대 NP 문제입니다.

배낭 문제의 결정 문제는 NP-완전입니다. 그래서 모든 입력에서 다항 시간에 푸는 방법은 알려져 있지 않습니다.

가장 큰 값을 묻는 원래 꼴은 NP-난해입니다. NP-완전 문제만큼 어렵거나 더 어려운 문제라는 뜻입니다.

결정 문제를 풀 수 있으면 V 를 바꿔 가며 물어 가장 큰 값을 찾을 수 있습니다. 반대로 가장 큰 값을 알면 결정 문제의 답도 바로 나옵니다. 한쪽을 풀면 다른 쪽도 풀리니 두 꼴은 어려움이 같습니다.

아래 그림은 두 꼴이 어느 모임에 들고 서로 어떻게 바뀌는지를 보입니다. 원래 꼴은 예나 아니오로 답하지 않아서 NP 밖에 놓입니다.

flowchart TD
    subgraph NP모임["NP · 답을 다항 시간에 확인하는 결정 문제"]
        D["NP-완전 · 배낭 결정 문제"]
    end
    O["NP-난해 · 가장 큰 값을 묻는 원래 꼴"]
    D -->|"V 를 바꿔 가며 묻는다"| O
    O -->|"가장 큰 값을 V 와 견준다"| D

입력이 하나 늘 때마다 몇 배씩 불어나는 시간을 지수 시간이라고 합니다. 후보를 전부 보는 풀이의 2ⁿ 이 그렇습니다.

앞의 표 풀이가 있는데도 어렵다고 하는 까닭은 의사 다항 시간이기 때문입니다. 표 풀이는 W 의 자릿수에 대해 지수 시간입니다. 이렇게 수가 작을 때만 빠르게 풀리는 NP-완전 문제를 약한 NP-완전(weakly NP-complete)이라고 합니다.

변형

배낭 문제는 조건을 조금 바꾼 변형이 여럿 있습니다. 무엇이 바뀌었느냐에 따라 푸는 방법도 달라집니다. 아래 표는 자주 만나는 변형입니다.

무한 배낭은 「걸리는 시간과 메모리」에서 행 하나로 줄일 때 피하던 일을 일부러 합니다. 행 하나로 한도를 작은 쪽부터 채우면 같은 물건을 여러 번 넣은 값이 섞입니다. 그 소절 그림의 ① 이 0-1 배낭에서는 틀린 값이었지만 무한 배낭에서는 바로 원하는 값입니다.

여러 가방에 모든 물건을 나눠 담으면서 가방 수를 줄이는 문제도 있습니다. 이름은 비슷해 보여도 묻는 것이 달라서 빈 패킹 문제로 따로 부릅니다.

큰 입력에서 고르는 방법

어떤 풀이를 고를지는 물건 수와 한도가 정합니다. 둘 가운데 어느 쪽이 작으냐를 먼저 봅니다.

물건이 적으면 후보를 다 보거나 분기 한정으로 덜 볼 수 있습니다. 한도가 작으면 표 풀이가 가장 곧습니다.

둘 다 크면 최적의 답을 포기하고 그에 가까운 답을 노립니다. 최적과 얼마나 가까운지를 보장하는 풀이를 근사 알고리즘이라고 합니다. 배낭 문제는 최적에 원하는 만큼 가까운 답을 다항 시간에 내는 근사 방법이 알려져 있습니다.

백엔드 일에서도 이런 문제가 자주 나옵니다. 서버 한 대의 CPU(Central Processing Unit, 중앙 처리 장치)가 8 코어라고 칩시다. 4 코어·우선순위 9, 3 코어·우선순위 5, 5 코어·우선순위 8 인 작업 가운데 무엇을 올릴지 고르는 일이 배낭 문제입니다.

코어 수가 무게입니다. 우선순위는 값입니다. 따져 보면 4 코어와 3 코어 작업을 올려 우선순위 합 14 를 얻는 것이 답입니다.

메모리 한도 안에서 캐시에 올릴 데이터를 고르는 일도 같은 문제입니다. 데이터 크기가 무게입니다. 캐시에 올려 원본까지 가지 않아도 되는 조회 수가 값입니다.

관련 항목

배낭 문제를 푸는 설계 기법

완전 탐색 · 동적 계획법 · 그리디 알고리즘 · 분기 한정 · 재귀 백트래킹 · 메모이제이션 · 근사 알고리즘 · 정수 선형 계획법

배낭 문제의 변형

분할 가능 배낭 문제 · 무한 배낭 문제 · 개수 제한 배낭 문제 · 다차원 배낭 문제 · 다중 배낭 문제

배낭 문제와 함께 꼽히는 조합 최적화 문제

부분집합 합 문제 · 동전 교환 문제 · 빈 패킹 문제 · 분할 문제 · 외판원 순회 · 작업 스케줄링

배낭 문제의 풀이를 받치는 성질

부분집합 · 점화식 · 최적 부분 구조 · 중복 부분 문제 · 탐욕 선택 속성

배낭 문제의 어려움을 재는 도구

빅오 표기법 · 시간 복잡도 · 공간 복잡도 · 다항 시간 · 지수 시간 · 의사 다항 시간 · 조합 폭발 · 복잡도 클래스 · NP-완전 · NP-난해 · P 대 NP 문제

배낭 문제가 속하는 상위 분류

조합 최적화 · 최적화 문제 · 결정 문제 · 알고리즘