배낭 문제
N 개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지고, 해당 물건을 배낭에 넣으면 V 만큼의 가치를 얻는다.
최대 K 만큼의 무게만을 넣을 수 있는 배낭이 있을 때, 배낭에 넣을 수 있는 물건들의 가치의 최대값을 구하여라.
위의 문제가 배낭 문제 입니다.
문제의 상황이나 디테일한 부분은 달라질 수 있겠지만 대게 가중치 W 와 값 V 가 주어지고 가중치의 합이 K를 넘지 않도록 물건들을 조합하여 V의 합이 최대가 되도록 구하는 문제로 정의할 수 있습니다.
Fractional Knapsack Problem
주어진 물건들이 분할 가능한 경우입니다.
물건들이 분할 가능하기 때문에 무게당 가치를 계산하여 높은 순서대로 배낭에 넣으면 K 까지 넣었을 때의 가치가 최대값 입니다.
즉, 그리디 알고리즘으로 해결합니다.
0-1 Knapsack Problem
주어진 물건들이 분할 불가능한 경우 입니다.
이번 글에서 다루게 될 문제입니다.
분할 가능한 경우와 달리 탐욕법(그리디 알고리즘)으로 해결할 수 없습니다. ( 간단하게 반례를 찾을 수 있습니다)
기본적으로 완전탐색을 생각해봅시다.
N개의 물건들이 각각 배낭에 들어갈지, 아닐지, 두 가지 경우의 수를 가지고 있습니다.
그렇다면 $O(2^n)$의 복잡도를 가지고 해결할 수 있습니다. 하지만 n이 조금만 커진다면 사용할 수 없는 방법입니다.
다른 접근 방법이 필요합니다.
해결 방법
결론을 먼저 말하면 배낭 문제는 다이나믹 프로그래밍으로 해결합니다.
전체 문제를 작은 문제로 다시 정의하여 해결하고, 다시 전체 문제를 해결합니다.
그렇다면 배낭문제를 작은 문제로 정의해봅시다.
배낭과 물건들이 위와같이 주어졌을 때
우리가 구해야 할 것은 10kg 수용 가능한 배낭의 최대 가치 합 입니다.
이를 한번에 알 수 없기 때문에 우리는 문제를 작게 만들어 줍니다.
예를 들어 첫번째 물건을 배낭에 넣었을 때의 상황을 살펴보겠습니다.
위와 같이 10kg 배낭에 첫번째 물건을 넣었을 때 최대 가치 합은 5kg 가방의 최대가치 합 + 4 와 같아집니다.
5kg 가방에 2kg 물건을 넣게 된다면
10kg 가방의 최대 가치 => 5kg 가방의 최대 가치 + 4 => 3kg 가방의 최대 가치 + 2 + 4 => ...
이런식으로 문제를 작게 정의하며 답을 찾고 전체 문제를 해결할 수 있기에 DP로 해결할 수 있습니다.
문제를 작게 정의할때 바뀌는 부분은 배낭의 수용가능 무게와 배낭에 들어간 물건의 종류 입니다.
배낭의 수용가능 무게가 변경될 때마다, 어떤 물건이 배낭에 들어갔는지에 따라 문제가 정의되고 그 값을 구해야 하기 때문에 이차원 배열을 만들어 해결합니다.
DP[ i ][ weight ]
: i 번째 물건까지 고려했을 때, 최대 수용가능한 무게가 weight 인 배낭의 최대 가치 합
i번째 물건을 고려할 때 두 가지 경우가 발생할 수 있습니다.
- 가방에 i 번째 물건을 못 넣는 경우 : weight < i.weight
- 가방에 i 번째 물건을 넣는 경우 : weight >= i.weight
경우 1.
가방에 해당 물건을 넣을 수 없기 때문에 최대 가치는 가방에 물건을 넣기 전인 i - 1 번째를 고려했을 때와 동일합니다.
DP[ i ][ weight ] = DP[ i - 1 ][ weight ]
경우 2.
가방에 해당 물건을 넣을 수 있다면 다시 두가지로 나눌 수 있습니다.
경우 2-1 : 현재 물건을 가방에 넣는다.
위에서 했던것 처럼 문제를 작게 만들 수 있습니다.
가방의 최대 수용 무게에서 현재 물건의 무게를 빼서 문제를 작게 만들어 줍니다.
smallWeight = weight - i.weight
DP[ i ][ weight ] = DP[ i - 1 ][ smallWeight ] + i.price
현재 물건은 반드시 가방에 넣었다는 가정이 있기 때문에
현재 물건의 무게를 뺀 나머지를 최대 무게로 하는 가방의 최대 가치 합을
현재 물건을 고려하기 이전 상태에서 결정합니다.
이렇게 최대 weight 무게를 넣을 수 있는 가방의 현재 물건을 가방에 넣었을 때의 최대가치 합을 구합니다.
경우 2-2 : 현재 물건을 가방에 넣지 않는다.
현재 물건을 가방에 넣지 않는다면 DP[ i ][ weight - 1 ]
와 동일한 값을 가지게 됩니다.
따라서
DP[ i ][ weight ] = DP[ i ][ weight - 1 ]
2-1 과 2-2 의 경우 중 우리는 더 큰 가치를 원하기 때문에
DP[ i ][ weight ] = max( DP[ i - 1 ][ smallWeight ] + i.price, DP[ i - 1 ][ weight ] )
이렇게 최종 점화식을 구할 수 있습니다.
문제에서 주어진 조건은 N개의 물건을 모두 고려하고, 최대 K 까지 수용가능한 배낭이므로
최종적으로 우리가 구해야할 값은 DP[ N ][ K ]이 됩니다.
구현
첫번째 물건부터 하나씩 고려하며 DP 테이블을 채워봅시다.
우선 물건을 하나도 고려하지 않았을 땐 어떤 배낭에도 넣을 수 없기 때문에 모두 0으로 초기화 해줍니다.
첫번째 물건을 고려할 때 물건의 무게가 5 이기 때문에
가방의 최대 수용 무게가 5보다 작다면 (weight < 5) 넣을 수 없어 DP[ weight ][ i - 1]의 값( = 0)을 가집니다.
가방의 최대 수용 무게가 5 이상이라면 (weight >= 5) 직관적으로 최대 가치는 4 임을 알 수 있지만 위의 점화식을 활용해 봅시다.
DP[ i ][ weight ] = max( DP[ i - 1 ][ weight - 5 ] + 4, DP[ i -1][ weight ] )
DP[ i ][ weight ] = max( 4, 0 )
두번째 물건도 고려하여 두번째 행도 채워봅시다.
세번째 행도 채워봅시다.
여기서
DP[3][7] = max( DP[2][5] + 2, DP[2][7] ) 임을 확인할 수 있습니다.
DP[3][9] = max( DP[2][7] + 2, DP[2][9] ) 도 확인 가능합니다.
마지막 행
관련 문제
https://www.acmicpc.net/problem/12865
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
#include <iostream>
#include <vector>
using namespace std;
int max(int a, int b) { return a > b ? a : b; }
int main()
{
cin.tie(0);
ios_base::sync_with_stdio(false);
int n, k;
vector<vector<int>> dp;
vector<pair<int, int>> stuff;
cin >> n >> k;
dp.assign(n+1, vector<int>(k+1, 0));
stuff.resize(n+1);
for (int i=1; i<n+1; ++i)
{
int weight, value;
cin >> weight >> value;
stuff[i] = {weight, value};
}
for (int i=1; i<n+1; ++i)
{
for (int j=1; j<k+1; ++j)
{
if (j - stuff[i].first < 0)
{
dp[i][j] = dp[i-1][j];
}
else
{
dp[i][j] = max(dp[i-1][j], dp[i-1][j - stuff[i].first] + stuff[i].second);
}
}
}
cout << dp[n][k] << endl;
return 0;
}
/*
i번째 물건을 넣은 배낭의 수용가능 무게가 j일 때의 최대 가치
*/
'알고리즘 & 자료구조' 카테고리의 다른 글
[알고리즘] 플로이드-워셜 (Floyd-Warshall) (1) | 2024.01.14 |
---|---|
[알고리즘] 크루스칼 알고리즘 (Kruskal Algorithm), C++ (0) | 2024.01.01 |
[알고리즘] 프림 알고리즘 (Prim's Algorithm), C++ (0) | 2023.12.10 |
[알고리즘] 최소 신장 트리 (MST, Minimun Spanning Tree) (0) | 2023.12.09 |
[알고리즘] TSP 외판원 순회 알고리즘 (1) | 2023.11.23 |