Knapsack 알고리즘

Knapsack 알고리즘

• 무게와 가치가 따로 있고 가져갈 수 있는 최대 가치를 묻는 문제에 사용

• 모든 경우를 다 따져보는 Greedy 알고리즘으로 해결할 수 있지만 시간복잡도가 2^n, 최적의 답일 보장 없음

• 다이나믹 프로그래밍으로 풀어야함

• w[i] : i 번째 보석의 무게

• v[i] : i 번째 보석의 가치

• d[i][j] : i 번째 보석까지 탐색한 현 상태, j 만큼 무게를 가져갔을 때 획득한 최대 가치

1. i 번째 보석을 가져간 경우 : d[i][j] = d[i-1][j-w[i]] + v[i]

2. i 번째 보석을 가져가지 않은 경우 : d[i][j] = d[i-1][j]

   i를 첫 번째 보석부터 n 번째 보석까지,
       j를 0kg부터 k (배낭이 담을 수 있는 최대 무게)까지
           d[i][j] = max(d[i][j], d[i-1][j-w[i] + v[i])

관련 문제

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

코드 구현

#include <iostream>
#include <algorithm>
using namespace std;
int d[101][100001];
int w[101];
int v[101];
int main()
{
    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; i++)
    {
        cin >> w[i] >> v[i];
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            d[i][j] = d[i - 1][j];
            if (j - w[i] >= 0)
            {
                d[i][j] = max(d[i][j], d[i - 1][j - w[i]] + v[i]);
            }
        }
    }
    cout << d[n][k];
}