[알고리즘] 평범한 배낭

구현 방식

• 동적계획법을 사용한다.
• acc[i][j] 는 i 번째 물품까지 탐색했을 때 무게 j 에서의 최대 가치 값을 의미한다.
• 점화식을 나타내면 아래와 같다.

acc[i][j] = max(acc[i-1][j], acc[i-1][j-w[i]] + w[i])

코드

• 최종 코드는 아래와 같다.

#include <bits/stdc++.h>

using namespace std;

void solution(int N, int K);
void dp(int N, int K);

// first : 무게 , second : 가치
pair<int, int> weights[100];
int acc[100][100001] = {};


int main() {
    int N, K;
    cin >> N >> K;
    for (int i = 0; i < N; i++)
    {
        cin >> weights[i].first;
        cin >> weights[i].second;
    }
    solution(N, K);
    return 0;
}


void solution(int N, int K)
{
    dp(N, K);
    int result = INT_MIN;
    for (int i = 0; i <= K; i++)
    {
        result = max(acc[N - 1][i], result);
    }
    cout << result;
}


void dp(int N, int K)
{

    if (weights[0].first <= K)
        acc[0][weights[0].first] = weights[0].second;
    for (int i = 1; i < N; i++)
    {
        for (int w = 0; w <= K; w++)
        {
            acc[i][w] = acc[i - 1][w];
            if (0 <= w - weights[i].first)
                acc[i][w] = max(acc[i][w], acc[i - 1][w - weights[i].first] + weights[i].second);
        }
    }


}