배낭 문제 (Knapsack problem)

작성중
기본적인 내용에 관한 글은 너무 많고, 고급 기법에 관해서는 아래 두 링크를 참고
- https://infossm.github.io/blog/2023/03/18/Knapsack/
- https://codeforces.com/blog/entry/98663
'이 문제는 냅색으로 푸면 된다', '냅색DP를 쓰면 된다' 이런 표현들을 흔히 쓰긴 하는데, 원래 배낭(=냅색) 문제는 알고리즘 이름이 아니라 문제 이름이다. 표현을 정확히 하자면 '냅색 문제를 풀듯이 풀면 된다' 이런 식이 될텐데.. 그냥 문제 이름에서 알고리즘 이름이 붙은 '불도저 트릭' 이나, '금광 세그' 등을 생각하면 뭐 냅색DP라는 표현 자체가 그렇게 말이 안될것도 없지 않나 싶기도 하다
- 별 관계는 없는 말이지만, 영어 '냅색'이란 단어를 여기에서 처음 들었다. 보통 배낭하면 가장 처음 떠오르는 단어는 백팩 아닌가? 배낭 대신 가방으로 생각해도 ~백 이런단어들이지.. 네이버 사전에 따르면 knapsack은 (작은)배낭이라고 한다.
하지만 어쨌든, 냅색 DP라는 표현을 쓰려면, 냅색 DP가 뭘 말하는지는 정확히 해둬야 할것 같다.
냅색 문제는 기본적으로 무게와 가치가 각각 다른 여러개의 물건이 있을때, 가방의 제한 용량을 넘지 않는 조건에서 가장 높은 가치를 지니도록 물건을 담는 방법의 문제이다. 이것을 물건의 개수에 대한 제한에 따라서 분류해보면
- Fractional knapsack: 물건을 마음대로 쪼갤수 있다. 냅색DP는 이 문제에 전혀 필요치 않고, 간단한 그리디로 풀린다. 굳이 설명 X
- 0-1 knapsack: 같은 종류의 물건을 0개 또는 1개만 담을수 있다. 이것이 일반적으로 부르는 냅색 문제의 표준 형태이다
- bounded knapsack: 같은 종류의 물건을 최대 n개까지 담을수 있다.
- unbounded knapsack: 같은 종류의 물건을 무게가 허락하는 한 무제한으로 담을수 있다.
- 등등이 있다
그리고, partition problem, subset sum problem 등도 냅색 문제의 특수 케이스로 분류할수 있다.
표준 형태인 0-1 knapsack은 원래 NP-hard 문제로 다항시간에 풀수 없는 문제이다. 완전탐색으로 O(2^n)으로 풀고, 백트래킹 과정에서 가지치기를 통해서 시간을 줄일수 있다.
하지만, 배낭의 크기 W가 작을 때에는, DP를 이용해서 O(nW)에 풀수 있다. 보통 우리가 냅색으로 풀었다, 냅색DP를 써서 풀었다고 표현하는 것은 이 방법을 사용해서 푸는 경우이다. 이것은 시간복잡도가 입력값의 갯수 n이 아니라 입력값 자체에 따라 결정되기 때문에 pseudo-polynomial time 알고리즘으로 분류된다. 이때의 핵심 아이디어는 모든 아이템 조합들 중에서 무게합이 w인 조합들을 묶어서, 그중에서 가치의 합의 최댓값을 저장해두는 것이다. 이런 형태로 데이터를 저장하면 아이템을 하나씩 늘려나가면서 점화식을 짜는 것이 가능하다.
문제를 일반화하면 무게합에 관한 제한 조건이나 구하는 값의 형태는 다양하게 변형될 수 있지만, 그런 문제들도 점화식을 만드는 핵심 아이디어가 같기 때문에 전부 그냥 냅색이라고 부른다…
- 무게합의 제한조건은, W이하 뿐 아니라, 정확히 W가 되거나, W이상이 되도록 바뀔수 있다.
- 구하는 값은 물건의 다른 속성값의 합의 최댓값 (=가치의 합의 최댓값) 뿐 아니라, 최솟값 (이 경우는 무게합의 제한조건이 W이상으로 주어진다), 무게합이 w가 되는 조합의 갯수, 무게합이 w일때 가질수 있는 모든 가치값들 등등으로 변형된다

0-1 Knapsack

가장 기본 유형이다. i번째 물체가 무게 w_i과 가치 v_i 을 가질때, 무게의 합이 배낭의 용량 W를 초과하지 않으면서 가치의 합이 최대가 되도록 물체들을 선택하는 것.
n이 작으면, 그냥 완전탐색을 쓴다
W가 작으면 동적 프로그래밍으로 풀수 있다
- dp[i][j]를 i번째 물체까지 확인해서 총 무게가 j가 되도록 배낭을 채웠을때 최대 가치로 잡자. 이것은 i번째 물체를 고르지 않았을때의 가치와 골랐을때의 가치중에 큰 값이 되므로, 점화식은 dp[i][j] = max(dp[i-1][j], dp[i-1][j - w_i] + v_i) 가 된다
- 구하는 답은 max_j(dp[n][j]) 가 된다
- 만약 모든 w_i가 k의 배수라면, w_i/k 를 무게로 생각해서 계산해도 된다. 시간복잡도가 O(n*W/k) 로 줄어든다.
- 모든 w_i가 k의 배수까지는 아니더라도, 만들어질수 있는 무게의 합들이 많이 스파스할 경우에는 dp테이블을 배열대신 dict를 써서 만드는것도 방법이다.
구현팁
- DP테이블은 2차원이지만, 일반적인 토글링 테크닉을 이용해서 길이 W짜리의 1차원 배열 2개로 계산할 수 있다. 그리고, 0-1 냅색의 점화식의 특징을 이용하면 그냥 길이 W짜리의 1차원 배열 1개로만 처리할수도 있다. 이렇게 처리할 경우 dp[i][j]를 채울때, j를 역순으로 순회하면서 채워야 한다는 것을 기억해두어야 한다.
- 기본적인 코드는 이런식이다
  - ```
  dp = [0] * (W + 1)
  for w_i, v_i in items:
      for w in range(W + 1, w_i - 1, -1):
          dp[w] = max(dp[w], dp[w - w_i] + v_i)
  answer = max(dp)
```
- 속도를 조금 더 빠르게 하려면, 인덱스 접근과 max 함수 호출을 줄여서 아래처럼 쓸수 있다. 이정도만 해도 많이 빨라진다
  - ```
  dp = [0] * (W + 1)
  for w_i, v_i in items:
      for w, dp_w in zip(range(W + 1, w_i - 1, -1), reversed(dp)):
          if (v := dp[w - w_i] + v_i) > dp_w:
              dp[w] = v
  answer = max(dp)
```
- 여기서 인덱스 접근을 더 줄이는 것도 가능하지만, 이제 속도 향상에 비해서 가독성의 저하가 너무 크다. 차라리 무게 합이 w일때의 가치를 dp[W-w]에 저장하는 식으로.. 즉 배열을 역순으로 저장하면 그나마 가독성을 어느정도 유지하면서 속도를 더 최적화시킬수 있다. (코드는 깔끔해 보이는데, 헷갈리지 않도록 주의를 해야 한다..) ⇒ 쓰다보니까 익숙해져서 안헷갈릴 자신이 생겼다; 그냥 항상 이 형태로 쓰자
  - ```
  dp = [0] * (W + 1)
  for w_i, v_i in items:
      for w, dp_w, dp_p in zip(range(W + 1), dp, dp[w_i:]):
          if dp_p + v_i > dp_w:
              dp[w] = dp_p + v_i
  answer = max(dp)
```
- dp table을 dict로 관리한다면 코드는 아래처럼 된다
  - ```
  dp = {0: 0}
  for w_i, v_i in items:
      dp_update = {}
      for w, v in dp.items():
          if w + w_i <= W and v + v_i > dp.get(w + w_i, 0):
              dp_update[w + w_i] = v + v_i
      dp.update(dp_update)
  answer = max(dp.values())
```

구하는 값에 대한 변형

용량조건에 관련된 변형

보통 풀게되는 것은 x값들의 합이 X이하인 조건을 만족할때 y값들의 최적값을 구하는 문제이다. 이것은 배낭 용량 이하의 모든 무게에 대해 계산된 dp값중에서 최댓값을 찾으면 되므로 max_i(dp[n][i]) 로 구하면 된다.
무게합이 배낭의 용량과 같도록 딱 맞춰서 채웠을때의 최댓값을 구하는 문제의 경우는, 그냥 dp[n][W] 가 답이 된다.
무게합이 배낭의 용량 이상일때에, 최적값을 구하는 문제도 있을 수 있다. 이때는 대개 최솟값을 구해야 하는 경우가 될것이다.
- 직관적인 방법은 dp테이블의 크기를 W + x 까지로 잡고 채워주는 것이다. (x는 가장 무거운 물건의 무게이다). 이렇게 처리하면, 범위만 다를뿐 똑같은 코드로 dp 테이블을 채울수 있고, 최종 답은 min_i>=W(dp[n][i]) 으로 구할수 있다.
- 위의 방식은 무게합이 W보다 클 경우에도 무게별로 최솟값을 갖고 있는 방식인데, 그러지 말고, 무게합이 W보다 큰 경우들은 모두 합쳐서 최솟값 하나로 통일해서 관리하는 것도 가능하다.
  - 아이템 (w_i, v_i)에 대해서 아래처럼 업데이트 해주면 된다.
    - answer = min(answer, min(dp[-w_i:]) + v_i)
    - 0-1 Knapsack에서는 (w_i, v_i)로 dp 테이블을 업데이트하기 전에 먼저 저 값을 처리해야하고, Unbounded knapsack에서는 dp테이블을 업데이트한 뒤에 저 값을 처리해준다
  - 1106

그 외의 변형

23748: 2차원으로 확장. sum(x)>X, sum(y)>Y 가 될때 sum(z)의 최솟값을 찾는 문제

Unbounded Knapsack

DP로 포뮬레이션하는 기본 형태는 0-1 knapsack 과 같다.
가치합을 최대화 하는 문제를 기준으로 설명하면
- dp[i][j]를 i번째 물체까지 확인해서 총 무게가 j가 되도록 배낭을 채웠을때 최대 가치로 잡으면 된다. 다만 점화식이 조금 달라진다.
  - dp[i][j] = max(dp[i-1][j], dp[i-1][j - w_i] + v_i, dp[i][j - w_i] + v_i) 가 된다
이것도 0-1 knapsack 처럼 메모리 사용량을 O(W)으로 줄일 수 있는데 방법이 거의 비슷하면서 약간만 달라서 헷갈리지 않게 주의해야 한다
- 그냥 일반적인 토글링 테크닉을 이용해서, 길이 W짜리의 1차원 배열 2개로 계산한다면 헷갈릴 여지가 없다.
- 1차원 배열 1개로 처리한다면, dp_i[j] = max(dp_i[j], dp_i[j - w_i] + v_i) 로 계산하면 되는데, 0-1 냅색에서는 j를 W부터 w_i까지 역순으로 채워나갔지만, unbounded에서는 j를 w_i에서 W까지 순서대로 채워나가야 한다.
- 기본적인 코드는 이런식이다
  - [코드]
바깥쪽 루프에서 물체들을 순회하고, 안쪽 루프에서 무게합을 순회하면서 테이블을 채우는 것이 정석이면서, 0-1 knapsack과 일관성을 갖는 방식이기도 하지만, 경우에 따라서는 안쪽 루프와 바깥쪽 루프를 바꾸어써도 문제를 푸는데에는 상관없다.
- dp[i] = F(dp[i-w[0]], dp[i-w[1]], dp[i-w[2]], …, dp[i-w[n]]) 같은 형식으로 이터레이션 할수 있다.
  - 이것은 인접 max(w_i) 항에 대한 점화식이므로, 인접 항들만 슬라이딩 윈도우 형태로 유지하면 다시 O(max(w_i))만큼의 메모리로 줄일수도 있다.
- 이 방법이 가능한 경우는 답이 물체를 고르는 순서에 영향을 받지 않는 경우이다. 정석대로 채우면 i번째 물체를 고를만큼 고른 이후에 i+1번째 물체를 고르는 상황만 고려하게 되지만, 이 방식으로 채우면 순서에 영향을 받지 않는다
  - 가치합의 최댓값을 구하는 경우를 비롯한 많은 경우에는 물체를 고르는 순서에 영향을 받지 않는다.
  - 그냥 무게합이 W가 되는 조합의 가짓수를 찾는 경우에는, 이 방식으로 하면 답이 전혀 달라진다. 1번 물체를 2개, 2번 물체를 1개 고르는 것을 모두 똑같이 1가지 방법으로 보는 것과, 1+1+2, 1+2+1, 2+1+1 의 세가지 다른 방법으로 보는 방법이 된다.
  - 무게가 1인 물체와 2인 물체를 가지고 무게 N을 만드는 방법의 갯수를 순서를 고려해서 생각하면 피보나치 수가 된다는 것은 너무 잘 알고 있다. 위에 처럼 점화식을 쓰면 그대로 dp[i]=dp[i-1]+dp[i-2] 라는 피보나치수의 점화식이 나온다.

문제들
- 가치합을 최대화 하기
  - 이때는 V를 기준으로 dp를 돌리기는 어렵다. W를 기준으로 하자
  - 연습문제
    - 4781
- Coin problem
  - 밑에 설명

Coin Problem

여러종류의 동전을 이용해서 특정 금액을 만드는 것에 관계된 문제. 최소 갯수의 동전으로 특정 금액을 만드는 문제 / 특정 금액을 만드는 방식의 가짓수를 찾는 문제 등이 있다.
- 용어가 가리키는 문제가 정확하게 정의된 것은 아니고, 흔히부르는 용어이다.
- 특정 금액을 만들수 있는 방법의 가짓수를 찾는 문제는 그냥 Coin change problem 이라고 부르는 경우가 많은것 같다.
- 특정 금액을 만들수 있는 동전 개수의 최솟값을 찾는 문제는 Minimum coin change problem 이라고 부르는 경우도 있고, 위키피디아에서는 Change-making problem 이라고 부른다.
  - 위키피디아에서는 Coin problem은 프로베니우스의 동전 문제를 가리키는 용어로 쓰이고 있다.
냅색 문제의 특수 케이스로 볼수 있다.
- 보통 사용가능한 동전의 갯수는 무제한으로 주어지는 경우가 많다. Unbounded knapsack.
- 동전의 금액이 물체의 무게에 대응된다.
- 동전의 갯수를 최소화 하는 문제는, 가치의 합을 최소화하는 문제에서 모든 물체의 가치가 모두 1인 경우라고 보면 된다

Coin Change Problem

특정 금액을 만들 수 있는 동전 조합의 가짓수를 찾는 문제. 각 종류의 동전들을 몇개씩 쓰느냐만 신경쓰고, 각 동전을 어떤 순서로 내는지는 구분하지 않는다.
Unbounded knapsack 에서 무게합이 W가 되는 조합의 개수를 찾는 문제와 같다.
코드 샘플은 동전 1 참고
관련 문제
- 동전 1, Coins, 동전: 다 비슷한 표준 형태의 문제
- 27519

Minimum coin change problem

특정 금액을 만들기 위해 필요한 최소한의 동전 갯수를 찾는 문제이다.
이 문제는 조건에 따라서 그리디 알고리즘의 예제로도 많이 사용되는 문제이다.
- 특수한 경우에는, 그냥 가장 비싼 동전부터 최대한 많이씩 사용하는 방식의 그리디 알고리즘으로도 최적값을 찾을수 있다. 이때의 시간복잡도는 동전들을 비싼 순으로 정렬하는 O(nlogn)에 바운드 된다.
- 이런 그리디 알고리즘이 성립하는 가장 흔한 경우는, 모든 동전들 사이에 배수 관계가 성립하는 것이다. 비싼동전이 싼 동전의 배수가 되는 경우로, 우리나라의 (1, 5, 10, 50, 100, 500) 시스템이 대표적인 예이다.
- 하지만 동전 시스템이 저 조건을 만족하지 않더라도, 그리디 알고리즘이 성립할수 있다. (1, 5, 10, 25, 50, 100)의 미국 동전이나, (1, 2, 5, 10, 20, 50, 100)의 캐나다 동전도 그리디 알고리즘이 성립하고, 실제로 어떤 나라에 존재하는 동전시스템은 대부분 그리디 알고리즘이 성립하게 되어있다.
- 일반적으로는 주어진 동전 종류를 보고 그리디로 풀수 있는지 아닌지를 판단하는 것은 간단하지 않다. 이렇게 그리디가 성립하는 동전 시스템을 Canonical 하다고 표현하는데, 주어진 시스템이 Canonical coin system인지 아닌지 여부를 판단하는 알고리즘은 O(n^3)에 동작한다고 한다. BOJ에 있는 15423 이 바로 그 문제다.
일반적으로는 냅색DP를 이용해서 푼다. (동전간에 배수관계가 성립하면 그리디, 아니면 냅색. 이렇게 접근하는게 편하다)
냅색DP로 변환하는 것은 앞에 다 설명했으니, 코드만 첨부하면 이런식이다.
- <code>

5585 : 주어진 동전 시스템은 캐노니컬하므로, 그리디하게 풀면 된다.
11047 : 동전 종류가 문제에서 고정된 것이 아니라 인풋으로 들어오지만, 비싼 동전이 싼 동전의 배수라는 조건이 있으므로 항상 캐노니컬하다. 그리디하게 풀면 된다.
2294 :
설탕 배달: 동전이 두종류밖에 없다. 이 경우는 케이스처리를 해주면 간단히 처리할수 있다

그룹에서 고르기

N종류의 물체들이 주어지는 대신에, 물체들의 그룹이 N개 주어진다. 각 그룹은 여러개의 물체를 포함하는데, 우리는 각 그룹에서 최대 한개의 물체만 골라서 담을 수 있다.
dp[i][j][k] 를
이 경우는 1차원 배열 1개만으로 dp 테이블을 갱신하기는 어렵다. 일반적인 방식으로 1차원 배열 2개를 이용해서 토글링하자.
18427

Bounded Knapsack

평범한배낭2 (12920)
1943

무게가 w인 물체를 갯수를 1,2,…,k개 중에서 선택해서 담은것은, 무게가 w, 2*w, 3*w, …, k*w 인 물체들이 한 그룹으로 주어졌을때 그룹에서 물체 한개를 골라서 담은것으로 볼수도 있다. 이렇게 처리하면 O(n*k*W) 이 된다
w, 2*w, 3*w, …, k*w 의 그룹으로 묶는 방법을 다시 잘 보면 등차수열. w로 나눈 나머지가 c 인 i들에 대해서만 채운다고 치면, 인접 k항에 대해서만 처리 되는 형태. O(nW) 가능
다른 접근법은, 무게가 w, 2*w, 4*w, 8*w, … 인 물체들이 1개씩 있는 상태로 보는 것. 이렇게 되면 logk개의 물체가 있는 0-1 knapsack 으로 변환된다. O(nWlogk)
- 물체들을 묶을 때의 원칙은, 묶인 물체들의 조합으로 모든 가능한 개수를 다 표현할수 있어야 하는것이다. 묶는 개수를 2의 거듭제곱 형태로 묶어주고 나머지들을 한번 더 묶어주면 가능하다.
  - 예를 들어 물체의 갯수가 20개라면, 1개, 2개, 4개, 8개를 만들고, 남은 4개를 다시 묶어서 만들어주면 된다.
- 주의할점은 이런식으로 구할때, 무게당 최대가치, 최소가치 등을 구하는 것은 가능하지만, 무게를 만드는 조합의 개수 등을 구할수는 없다는 것이다.
  - 음.. 좀더 신경쓰면 어떻게 가능할거 같긴 한데 나중에 닥치면 생각해보자;

유형분류

0-1 knapsack

	조합의 존재여부	V합의 최댓값	V합의 최솟값	기타
무게합이 W 이하일때		16493
무게합이 정확히 W일때	subset sum		22115 (v는 모두 1)	32382
무게합이 W 이상일때			23748

기타 합이 정확히 W일때, 아이템의 개수별 조합의 개수 : 32382

Unbounded

	V합의 최댓값	V합의 최솟값	가능한 조합의 가짓수
합이 W 이하일때
합이 정확히 W일때		Minimum coin change problem	Coin Change Problem
합이 W 이상일때		1106

Subset Sum Problem

subset sum problem(SSP)
정수의 집합이 주어졌을때, 부분집합중 합이 W가 되는 것을 찾는 문제
배낭문제의 특수 케이스라고도 볼수 있다.
- 모든 아이템은 무게=가치 이고, 가방의 용량이 W인 경우를 생각하면 된다.
배낭문제와 마찬가지로, n이 작으면 완전탐색, W가 작으면 DP를 이용한다
n≤40 정도의 범위까지는 완전탐색으로 풀수 있다.
- n≤20 정도면, 그냥 단순히 모든 부분집합을 다 나열해보는 O(2^n) 방법으로도 풀수 있다.
- 그보다 크면, Meet in the middle 방법을 사용해서 좀더 효율적으로 O(2^(n/2)) 에 해결할수 있다.
  - 위키피디아에 의하면 Horowitz and Sahni가 개발한 알고리즘이라고 한다
DP로 계산하는 방법은 배낭문제와 비슷하다 (음수가 섞여있을때
- 기본적인 방법은 O(nW) 이 걸린다.
- 부분집합의 존재여부만 확인하는 것이라면 bitset을 이용해서 최적화가 가능하다. O(nW/64) 로 최적화 가능
- 모든 원소가 C이하라면, Pisinger의 알고리즘을 이용해서 O(NC) 에 계산 가능 (솔브드 기준 루비난이도)

완전탐색

대충 가능한 n의 범위는 최대 40정도이다.
Meet in the middle 방법을 사용해서 풀어야 할텐데, 이보다 더 커지면 시간도 시간이지만 메모리도 초과되게 된다.
위키피디아의 설명에 따르면, 일반적으로 우리가 아는 meet in the middle 방법인 Horowitz and Sahni 방법으로는 메모리 한계로 최대 50개 정도가 한계이지만, 메모리 사용량을 개선한 Schroeppel and Shamir 방법으로는 최대 100개 정도까지 해결가능하다고 한다

Meet in the middle 방법을 이용해서, 부분집합의 갯수를 찾는 코드는 대충 이런 식이다.

def count_subset(nums, target):
    first, second = nums[: len(nums) // 2], nums[len(nums) // 2 :]
    first_sums, second_sums = [0], [0]
    for num in first:
        first_sums.extend([num + x for x in first_sums])
    for num in second:
        second_sums.extend([num + x for x in second_sums])
    second_counter = collections.Counter(second)

    ret = sum(second_counter[target - x] for x in first_sums)
    if target == 0:
        ret -= 1
    return ret

n≤40 기준으로 메모리 제한이 128mb이라면 (파이썬이면 실제로는 288mb까지 허용), 추가로 저장하는 정보량에 따라서 메모리가 초과될수도 있다. 이때는 한쪽 절반에 대한 sum만 저장해두고, 다른쪽 절반은 그냥 백트래킹하면서 찾는 방식으로 메모리 사용량을 줄일수 있다.

def count_subset2(nums, target):
    first, second = nums[: len(nums) // 2], nums[len(nums) // 2 :]
    first_sums = [0]
    for num in first:
        first_sums.extend([num + x for x in first_sums])
    counter = collections.Counter(first_sums)

    second_sums_iter = subsets(second, 0, lambda s, num: s + num)
    ret = sum(counter[target - x] for x, _ in second_sums_iter)
    if target == 0:
        ret -= 1
    return ret

관련 문제
- 부분수열의 합 2: n≤40, 합이 W가 되는 부분집합의 갯수를 구한다.
- 1450: n≤30, 합이 W이하가 되는 부분집합의 갯수를 구한다.
- 암호문: n≤40, 합이 W가 되는 부분집합을 찾는다.

문제집의 문제 분류

9084 (=3067):Coin Change Problem

목차