이 문제는 주어진 제약 조건 아래에서 최적의 구매 조합을 찾는 것이다.

입력 형식

• 첫째 줄: 전체 예산 n과 물품 수 m
• 다음 m줄: 각 줄은 vᵢ(가격), pᵢ(중요도), qᵢ(소속 주요 항목 번호)로 구성됨
• qᵢ = 0이면 해당 물품은 주요 항목임

출력 형식

• 최대 가치(가격 × 중요도 합계)를 출력

예시 입력/출력

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

2200

풀이 전략

이 문제는 그룹 배낭 문제(Group Knapsack)의 변형이다.

• 각 주요 항목과 그 보조 항목들로 이루어진 그룹을 구성한다.
• 각 그룹에서 선택 가능한 조합은 다음과 같다:
  1. 주요 항목만 구매
  2. 주요 항목 + 첫 번째 보조 항목
  3. 주요 항목 + 두 번째 보조 항목
  4. 주요 항목 + 두 보조 항목 모두
• 각 그룹은 단 하나의 조합만 선택 가능하다.

동적 계획법 설계

• f[j]: j 원의 예산으로 얻을 수 있는 최대 가치
• 주요 항목을 순차적으로 처리하면서, j를 n에서 v[i]까지 감소시키며 갱신
• 각 주요 항목에 대해 가능한 모든 조합을 시도하여 f[j]를 업데이트

코드 구현

#include <bits/stdc++.h>
using namespace std;

int n, m;
int price[65], importance[65], parent[65];
int dp[32005];
vector<int> attachments[65]; // 각 주요 항목의 보조 항목 리스트

int main() {
    cin >> n >> m;

    // 입력 및 보조 항목 정리
    for (int i = 1; i <= m; ++i) {
        cin >> price[i] >> importance[i] >> parent[i];
        if (parent[i] != 0) {
            attachments[parent[i]].push_back(i);
        }
    }

    // 동적 계획법 수행
    for (int i = 1; i <= m; ++i) {
        if (parent[i] != 0) continue; // 보조 항목은 건너뜀

        // 현재 주요 항목의 가격과 가치
        int base_cost = price[i];
        int base_value = base_cost * importance[i];

        // 역순 탐색 (0/1 배낭)
        for (int j = n; j >= base_cost; --j) {
            int remaining = j - base_cost;

            // 1. 주요 항목만 구매
            dp[j] = max(dp[j], dp[remaining] + base_value);

            // 2. 주요 항목 + 첫 번째 보조 항목
            if (!attachments[i].empty()) {
                int first = attachments[i][0];
                if (remaining >= price[first]) {
                    dp[j] = max(dp[j], dp[remaining - price[first]] + base_value + price[first] * importance[first]);
                }
            }

            // 3. 주요 항목 + 두 번째 보조 항목
            if (attachments[i].size() >= 2) {
                int first = attachments[i][0], second = attachments[i][1];
                // 두 보조 항목 모두 포함
                if (remaining >= price[first] + price[second]) {
                    dp[j] = max(dp[j], dp[remaining - price[first] - price[second]] + base_value + price[first] * importance[first] + price[second] * importance[second]);
                }
                // 두 번째 보조 항목만 포함 (첫 번째는 생략)
                if (remaining >= price[second]) {
                    dp[j] = max(dp[j], dp[remaining - price[second]] + base_value + price[second] * importance[second]);
                }
            }
        }
    }

    cout << dp[n] << endl;
    return 0;
}

시간 복잡도 분석

• 주요 항목 수 ≤ 60
• 예산 한도 ≤ 32,000
• 각 그룹당 최대 4가지 조합 검사
• 총 시간 복잡도: O(m × n × 4) ≈ 7.68 × 10⁶
• 실제로는 충분히 효율적인 성능을 제공

결론

이 문제는 물품 간 종속 관계를 고려한 그룹 배낭 알고리즘을 활용하여 해결할 수 있다. 주요 항목과 보조 항목의 조합을 사전에 정리하고, 동적 계획법으로 최적 해를 도출하는 것이 핵심이다.