[Algorithm] 0-1 KnapSack Problem

조재훈·2024년 10월 17일

algorithm ps

0-1 KnapSack Problem

흔히 배낭 알고리즘이라고 불리는, 이 문제는 n개의 물건과 배낭이 있을 때, 물건에는 각각 무게와 가치가 있다

배낭에 들어갈 수 있는 최대 무게가 있어 배낭의 최대 무게를 초과하지 않으면서 물건들을 배낭에 담아 만들 수 있는 최대 가치의 합을 찾는 문제이다

배낭 문제는 물건을 자를 수 있으면 Fractional KnapSack Problem이고, 자를 수 없으면 0-1 KnapSack Problem이다

여기선 자를 수 없는 경우를 다뤄보겠다

예제

백준 12865번 : 평범한 배낭

접근

처음에는 우선순위 큐를 이용해 그리디로 접근하려 했다가 안된다는 걸 깨달았다

그래서 구글링을 통해 찾아보니까 DP로 풀어야 하고 이런 알고리즘을 푸는 방법이 따로 있다고 한다

배낭 알고리즘이 DP인 이유는
물건을 배낭에 넣느냐 마느냐에 관한 문제이다. 1번째 물건을 배낭에 넣느냐 마느냐, 두 번째 물건을 넣느냐 마느냐에 따라 최대 합이 달라짐

최대 K까지 담을 수 있는 배낭이 있고 물건을 담을 때 선택할 수 있는 경우의 수는 2개이다

물건을 넣어서 (배낭 최대 용량 - 선택한 물건의 무게)
물건을 안넣고 배낭 최대 용량

이 과정을 모든 물건에 대해 반복하는 것이다. 가방에 더 이상 공간이 없을 때까지

코드

#include <bits/stdc++.h>

using namespace std;

int N, K;
int W[104], V[104]; // i번째 물건의 무게, 가치
int dp[100004];

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

    for (int i = 1; i <= N; i++)
    {
        int w, v;
        cin >> w >> v;
        W[i] = w; V[i] = v;
    }
    
    for (int i = 1; i <= N; i++)
    {
        for (int w = K; w >= W[i]; w--)
        {
            dp[w] = max(dp[w], dp[w - W[i]] + V[i]);
        }
    }

    cout << dp[K];

    return 0;
}