기본 배낭 문제

배낭의 최대 용량과 다양한 무게 및 가치를 가진 아이템들이 주어졌을 때, 배낭에 담을 수 있는 최대 가치를 구하는 문제입니다.

문제 설명

• 첫째 줄: 두 정수 M(배낭 용량)과 N(아이템 개수)
• 둘째 줄부터 N+1번째 줄까지: 각 아이템의 무게와 가치
• 출력: 배낭에 담을 수 있는 최대 가치

예시 입력

10 4
2 1
3 3
4 5
7 9

예시 출력

12

해결 전략

dp 배열을 사용하여 각 단계에서 선택할지 여부를 결정합니다. dp[i][j]는 i번째 아이템까지 고려했을 때, 용량 j를 가진 배낭에 담을 수 있는 최대 가치를 의미합니다.

코드 예시

#include <iostream>
using namespace std;

int main() {
    int capacity, itemCount;
    cin >> capacity >> itemCount;
    
    int weights[itemCount + 1], values[itemCount + 1];
    for (int i = 1; i <= itemCount; ++i) {
        cin >> weights[i] >> values[i];
    }
    
    int dp[itemCount + 1][capacity + 1];
    for (int i = 0; i <= itemCount; ++i) {
        for (int j = 0; j <= capacity; ++j) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (j >= weights[i]) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    
    cout << dp[itemCount][capacity];
    return 0;
}

완전 배낭 문제

각 아이템은 무제한으로 선택할 수 있습니다. 이 경우에도 최대 가치를 찾아야 합니다.

코드 예시

#include <iostream>
using namespace std;

int main() {
    int capacity, itemCount;
    cin >> capacity >> itemCount;
    
    int weights[itemCount + 1], values[itemCount + 1];
    for (int i = 1; i <= itemCount; ++i) {
        cin >> weights[i] >> values[i];
    }
    
    int dp[capacity + 1];
    for (int j = 0; j <= capacity; ++j) {
        dp[j] = 0;
    }
    
    for (int i = 1; i <= itemCount; ++i) {
        for (int j = weights[i]; j <= capacity; ++j) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    
    cout << "max=" << dp[capacity];
    return 0;
}

그룹 배낭 문제

아이템들은 여러 그룹으로 나뉘어 있으며, 각 그룹당 하나의 아이템만 선택할 수 있습니다.

코드 예시

#include <iostream>
using namespace std;

int main() {
    int capacity, itemCount, groupCount;
    cin >> capacity >> itemCount >> groupCount;
    
    int weights[itemCount + 1], values[itemCount + 1], groups[itemCount + 1];
    for (int i = 1; i <= itemCount; ++i) {
        cin >> weights[i] >> values[i] >> groups[i];
    }
    
    int dp[groupCount + 1][capacity + 1];
    for (int g = 0; g <= groupCount; ++g) {
        for (int j = 0; j <= capacity; ++j) {
            dp[g][j] = 0;
        }
    }
    
    for (int g = 1; g <= groupCount; ++g) {
        for (int j = 0; j <= capacity; ++j) {
            int maxValue = dp[g - 1][j];
            for (int i = 1; i <= itemCount; ++i) {
                if (groups[i] == g && j >= weights[i]) {
                    maxValue = max(maxValue, dp[g - 1][j - weights[i]] + values[i]);
                }
            }
            dp[g][j] = maxValue;
        }
    }
    
    cout << dp[groupCount][capacity];
    return 0;
}