knapsack 알고리즘 (백준 1535 , 4781 , 7579 )

knapsack은 "제한된 자원" 으로 "최적(최대 or 최소) 의 이득" 을 얻는 문제에서 사용된다. 아래는 대표적인 예시 중 하나다.

 

n개의 보석이있다. 이중 1~ n번째 보석중 k 번째 보석의 무게를 w_k, 가격을 c_k 라고 정의한다. 내가 가방에 최대로 담을 수 있는 무게가 w_max일때, 내가 담을 수 있는 최대 가치는?

 

대충 이런 느낌이지만, knapsack도 상황에 따라 다양한 방식으로 나눠져 있으므로 지금부터 같이 하나하나 알아보자!

 

 

 

 

1) fractional knapsack

 - 보석을 쪼개서 가방에 담을 수 있다.

>> 그냥 무게당 가치가 높은것들을 우선적으로 가방에 담으면 끝이다.

예를들어 무게3에 가치 9, 무게 2에 가치 4 무게 1에 가치 1인 보석이있다고하면

1번의 무게 1당 가치는 3, 2번은 2, 3번은 1이다.

만약 내가 최대로 챙길수 있는 무게가 4라고 하면, 무게당 가치가 높은 1번보석을 3만큼 담고, 남은 1만큼은

2번보석을 1의 무게만큼 챙기면 된다. 이경우 9+2 = 11의가치가 내가 가질 수 있는 최대 가치이다. 

 

 

2)0-1 knapsack

-각 종류의 보석은 1개만 존재한다.

우리가 knapsack 하면 떠올리는 대표적인 문제이다. 이는 dp 배열을 통해서 풀면 된다

dp[k][w] = 크기 w의 배낭안에 1~k번 보석까지, k개의 보석을 확인해 담았을 때의 최대가치를 저장한다.

배낭의 무게가 w 남았고, k번째 보석까지 확인하여 dp[k][w] 까지 채웠다고 가정해보자.

다음 보석인 k+1째 보석을 채울 때, 우리는 2가지 행동만 고려하면 된다. k+1 째 보석을 담거나, 담지 않거나.

이제 위의 2가지 행동을, 2가지의 상황에서 고려해보자.

 

만약 가방에 여유 무게가 없어 담을 수 없다면? 선택지는 "담지 않는다" 뿐이다.

 

만약 가방에 여유무게가 있어 담을 수 있다면? 선택지는 "담는다"  그리고 "담지 않는다" . ( 담지 않아서 여유 무게를 남겨두는게 최적의 값을 반환할 수 있다!)

 

 

1) k+1째 보석을 담을 수 없다면?

dp[k+1][w]=dp[k][w] 로 이전 dp 배열 값을 그대로 넣어주면 된다.( 보석을 담지 않으므로 남은 무게와 누적 가치 모두 그대로)

 

2) 만약 k+1째 보석을 담을 수 있다면?

담을것인가? 아니면 담을 수 있어도 담지 않을 것인가? ( 해당 보석을 담지 않는게 더 최적의 값일 수 있다.)

각 경우를 확인해보자.

 

k+1째 보석을 담는 경우의 최대 가치는

1~k째 보석을 사용하여 기존무게-k+1째(새로담는)  보석무게 만큼을 채운 최대 가치 + 새로 담는 보석 가치이다.

이를 dp로 표현시    dp[k+1][w]=dp[k][w-w_(k+1)] +c_(k+1)

 

 

그리고 만약 담지 않는다면 1) 에서 한것 처럼 dp[k+1][w]=dp[k][w] 로 이전 값을 그대로 가져오면 된다.

 

이 2가지 경우의 수를가지고 우리는 주어진 모든 보석에 대하여 해당 보석을 담는것과 담지 않는 것중 더 높은 가치를 가지는 경우를 채택하며 나아가면 된다. 이를 한줄로 표현하면 아래와 같다.

dp[k+1][w]=max(dp[k][w],dp[k][w-w_(k+1)]+c_(k+1) ) .

 

이를 응용하는 실제 예시를 아래 코드와 함께 살펴보자

int N,W;
int w[n_max], c[n_max]//w,c 배열은 편의상 0부터 시작이 아닌 1부터 시작한다고 정의.
int dp[n_max][w_max];
for(int k=0;k<N;k++){
	for(int w=1;w<=W;w++){
    	if(w-w[k+1]>=0)// k+1째 보석을 담을 공간이 있는가? 
    		dp[k+1][w]=max(dp[k][w],dp[k][w-w[k+1]]+c[k+1]);
        else
        	dp[k+1][w]=dp[k][w];//담을 공간없으면 담지 않고 패스.
    }
}

이렇게 담을수 있나 없나, 그리고 담는다면 이것이 해당 무게에서 최적인가? 를 찾은 뒤 결과 값은 

dp[n][w_max] ( n개 보석을 w_mak무게 만큼 사용했을때 최대 가치)  에 저장되어있다. 아래는 백준 1535번 '안녕' 문제이다. 풀어본 뒤 정답을 확인해보자.

 

#include <iostream>
using namespace std;
int N;
int L[101], J[101];
int dp[101][101];


int main()
{
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
 
    for (int i=1; i<=N; i++)
        cin >> L[i];
    for (int i=1; i<=N; i++)
        cin >> J[i];

    for (int i=1; i<=N; i++) {
        for (int j=1; j<=100; j++) {
            
            if (j-L[i] > 0)  // i 번째 사람에게 인사를 할 수 있을 때.
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-L[i]]+J[i]);
            else
            	dp[i][j] = dp[i-1][j];// 인사 가능시 

            
        }
    }
 
    cout << dp[N][100] << endl;
}

체력= 무게, 기쁨= 가치 로 치환하면 바로풀리는 문제이다.

 

주의할 점: "제한" 이 존재하는 것을 무게로 두자.

 

체력은 1~100 이므로, 이를 무게로 차환해서 구하자! 

 

3)unbounded knapsack

-각종류별 보석을 마음껏 사용가능.

즉 k번째 보석이 있다고 했을 때, 해당 보석을 2번 이상도 사용할 수 있다는 거다. 그럼 2번케이스와 어떻게 다르게 짜면 될까? 다시 보석을 담을 때 고려할 사항으로 돌아가보자. 담는다, 담지 않는다 2가지 외엔 여전히 존재할 수 없다.

 

1) 담지 않는다의 경우, 변함 없다.

 

2)담는다의 경우에서 변화가 생기게 된다.

보석을 종류별로 1개씩만 담을때는, 내가 어떤 보석을 담을때, 같은 종류의 보석이 이미 담겨있지 않다는 전제하에 동작한다. 하지만 이번케이스엔 내가 어떤 보석을 추가하는 것을 고려할때, 무게가 오버되는 것, 그리고 가치가 떨어지는 것, 이 두개만 고려하면 되고, 내가 '무슨 보석을 사용하는지' 는 제한 조건이 되지 않는다. 즉 dp 배열을 생성 될때

'몇번째 보석까지 사용했는지' 에 관한 것은 제거하고, 무게에 대한 dp만 생성해주면 된다. 

 

아래 백준 4781번을 보면서 어떻게 바뀌었는지 확인해보자! (우선 다른부분 생략하고 dp배열 쪽만 확인할 것!)

 

#include<iostream>
#include<algorithm>
using namespace std;
int c[10001];
int p[10001];
int dp[10001];


int main() {
	int n,m;
	double tmp;
	while (1) {
		for (int i = 0; i < 10001; i++) {
			c[i] = 0;
			p[i] = 0;
			dp[i] = 0;
		}
		
		cin >>n>> tmp;
        
		if (n == 0 && tmp == 0.00)
			break;
            
		m = (int)(tmp * 100.0+0.5);
		
		for (int i = 0; i < n; i++) {

			cin >> c[i] >> tmp;
			p[i] = (int)(tmp * 100.0+0.5);
		}

		for (int i = 0; i < n; i++) {
			for (int j = 1; j <= m; j++) {
				if (j - p[i] >= 0) {
					dp[j] = max(dp[j - p[i]] + c[i], dp[j]);//이부분 중요!
				}

			}
		}
		/*      				
		int ma = -1;
		for (int i = 0; i <= m; i++) {
			if (ma < dp[i])
				ma = dp[i];

		}
		*/
		cout << dp[m] << endl;// 왜 위의 주석에서처럼 최댓값을 안찾고 dp[m]을 출력하면 정답이
	}						  //나올지 생각해보자!
	 
	
}

 

앞서 설명했듯이 그저 현재 내가 탐색한 i째 사탕을 포함하는가, 포함하지 않는가 이 2가지 경우로 dp배열을 생성한 것이다. 이 문제에서 아마 아래 코드를 보며 이상했을 것이다.

 

m = (int)(tmp * 100.0+0.5);

 

이는  부동소수점에 관한 문제이다. '돈'으로 들어오는 값들이 소수점 둘째 자리까지 입력으로 들어오는데, 이를 정수로 바꾸기 위해 100을 곱해준다. 그런데 그 과정에서 rounding error가 발생할 수 있기 때문에 0.5를 더해주어 반올림 보정을 해주어야 오류없이 정답이 나오게 된다. 

 

 

 

 

마지막으로 좋은 knapsack 문제가 있어 가져왔다. 백준 문제 7579번을 보고오자! 

이 문제를 보고 1차원적으로 생각했다면( 내가 그랬다..) 당연히 바이트가 무게로 치환되서 knapsack을 풀었을 것이다.

나같은 경우는 일반적인 knapsack의 dp 파트를 아래와 같이 변형하여 풀었었다.( dp배열의 기본 값은 min함수 갱신을 위해 무한값( 987654321)으로 설정했다.

 

dp[k+ 1][w] =min(dp[k][w], dp[k][w - weight[k + 1]] + c[k + 1])

 

여기서 문제점이 2개 나오게 된다

 

1)디폴트가 무한값이어야 값이 min()함수를 통해 최솟값이 갱신이 되지만, 이 무한값(0이아닌 수)에 c[k+1] 값이 누적되게 됨으로, 쓸 수 없는 값이 되어버린다. 이게 첫번째 문제이다

 

2) 이 방식은 M을 초과하면 안되는 일반적인 배낭 문제와 달리 M보다 작으면 안되며, 가치의 최대가 되도록 하는 배낭과는 반대로 비용이 최소가 되어야 한다. 따라서 우리는 M까지만 dp를 탐색하는 기존 배낭 문제와 다르게 우리가 도달할 수 있는 최대 바이트까지(모든 입력 바이트값의 합) 탐색을 해야하고, 바이트의 크기는 1000만*100=10억 이되기에 시간초과가난다(보통 백준에선 1억연산이상이면 시간초과). 따라서 관점을 바꿔야한다.

'무게에 따른 비용' 이 아닌 '비용에 따른 무게' 로.

 

dp[k][c]>> k번째 앱까지 탐색하였을 때 c의 비용을 지불하여 얻을 수 있는 최대 메모리.

 

이렇게 dp를 설정하여 기존 knapsack문제처럼 dp를 완성한뒤, 가장 낮은 c값에서 W이상의 값을 가지는 dp를 찾아주면 된다. 아래는 정답코드이다.

 

#include<iostream>
#include<algorithm>
using namespace std;
//knapsack 은 최소비용으로 가는순간 복잡해진다.
int N, M, ans, sum;
int b[101], c[101];
int dp[101][10001];

int main()
{
	cin >> N >> M;

	for (int i = 1; i <= N; i++) cin >> b[i];
	for (int i = 1; i <= N; i++)
	{
		cin >> c[i];
		sum += c[i];//비용 max 값
	}

	// dp[i][j] == i번째 앱까지 탐색했을 때 j비용을 소모해서 얻을 수 있는 최대 메모리
	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j <= sum; j++)
		{
			if (j - c[i] >= 0)
				dp[i][j] = max(dp[i][j], dp[i - 1][j - c[i]] + b[i]);

			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
		}
	}

	for (int i = 0; i <= sum; i++)//낮은 비용> 높은 비용 탐색
	{
		if (dp[N][i] >= M)//M이상의 메모리 가지면 종료( 가장먼저 찾아진놈이 최소비용)
		{
			cout << i << endl;
			break;
		}
	}


}

 

 

 

끝으로 knapsack 문제에 대해 느낀 점이 하나 있다. 'knapsack 처럼 보이는 문제' 에 낚이지 말자 knapsack의 조건은 '정해진 무게 이하' 를 담을때 '최대비용' 이다.7579번도 knapsack으로 생각해서 어려웠던거지, 애초에 dp로 생각하고 풀었으면 바이트= 무게, 비용= 비용 의 뻘짓을 안하고 시간복잡도보고 대충 바이트 기준 탐색하면 안되는구나~ 하고 비용 기준으로 풀었을 것 같다..