[KnapSack] 백준 1495:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M, S;
    cin >> N >> S >> M;

    vector<int> volume(N);
    for (int i = 0; i < N; i++)
    {
        cin >> volume(i);
    }

    vector<vector<int>> dp(N + 1, vector<int>(M + 1));
    dp(0)(S) = 1;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 0; j <= M; j++)
        {
            if (dp(i - 1)(j) == 1)
            {
                S = j;
                if (S - volume(i - 1) >= 0)
                {
                    dp(i)(S - volume(i - 1)) = 1;
                }
                if (S + volume(i - 1) <= M)
                {
                    dp(i)(S + volume(i - 1)) = 1;
                }
            }
        }
    }

    for (int i = M; i >= 0; i--)
    {
        if (dp(N)(i) == 1)
        {
            cout << i;
            return 0;
        }
    }

    cout << -1;
}

1495번: 기타리스트(acmicpc.net)

1. 곡의 수 N은 50개까지이고, 곡이 지날 때마다 음량을 증감시켜야 하므로 모든 경우의 수는 2^50으로 모든 경우를 셀 수 없을 정도로 많다.

2. 그래서 dp(노래)(볼륨) 배열을 만들고 이전 볼륨을 얻을 때마다 다음 노래로 전환할 때 볼륨 배열에서 더하거나 뺀 값이 0과 최대값 사이에 있는지 확인하고 그렇다면 적절한 범주에 있습니다.

그렇다면 dp(현재 노래)(볼륨)를 1로 설정하십시오.

3. 마지막 곡의 최대 음량을 찾는 것이 문제이므로 dp(마지막 곡)(i) == 1인 곡 중에서 가장 큰 값 i를 출력한다.

이와 같이 1. 너무 많은 것이 무차별 대입되고 2. 선택할 수 있는 용량이 제한될 때 실행되는 dp 알고리즘을 배낭(knapsack)이라고 합니다.

사실 오늘 처음 배운 개념이라 아직 설명이 부족하지만 맞는지 모르겠습니다.

어쨌든, 이것은 대학 게시물이기 때문에 몇 가지 배낭 작업을 더 수행하여 다듬어 보겠습니다.