[c++] BOJ 12865 :: 평범한 배낭

난이도 : 골드 5

걸린 시간 : 1시간 반 이상

 

문제

문제 바로가기

 

오답

처음에 완전탐색으로 하되 최대한 조합의 범위를 줄여서 구현해보았다.

하지만, 시간 초과로 실패..!

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 6시 4분 시작 => 6시 42분 중단, 11시 12분 시작 =>
// N <= 10^2, K <= 10^5, W <= 10^5, V <= 10^3
// N : 물품 수, K : 무게, W : 무게, V : 가치
// 4개 7무게까지 가능
// K무게를 넘지 않는 선에서 가치합의 최대를 구하기

// 완전 탐색으로 했다면 주어진 물건들을 조합해서 무게가 K 이하인 조합들 중 가치가 가장 높은 경우를 찾기
// 무게가 같은 거는 가치가 높은 것만 냅두면 됨
// 무게 순으로 정렬해서 무게가 같거나 크면 다음거는 안해도 되게 (추가)
// 무게가 다른 것만 남음
// 작은 것부터 더해서 K 넘을 때까지 더해보기 => 갯수의 최대 구하기
// 큰 것부터 더해서 K 넘을 때까지 더해보기 => 갯수의 최소 구하기
// 최소 갯수 ~ 최대 갯수까지 조합을 해보기

vector<pair<int, int>> vec;
bool compare(pair<int,int> w, pair<int, int> v) {
    return w.first <= v.first;
}

int main() {
    // get input
    int N, K;
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        int w, v;
        cin >> w >> v;
        vec.push_back(make_pair(w, v));
    }

    // 무게 순 정렬
    sort(vec.begin(), vec.end(), compare);

    // 무게는 같은데 가치가 작은 것은 없애기
    for (int i = 1; i < vec.size(); i++) {
        if (vec[i - 1].first == vec[i].first) {
            int eraseIdx = -1;
            if (vec[i - 1].second < vec[i].second)
                eraseIdx = i - 1;
            else
                eraseIdx = i;
            vec.erase(vec.begin() + eraseIdx);
        }
    }

    // 필요한 갯수 범위 구하기
    int min_num, max_num;
    int tmp_sum = 0; int i = 0;
        // 작은 것부터 더해보아서 필요한 조합의 최대 갯수 구하기
    while (tmp_sum <= K) {
        tmp_sum += vec[i++].first;
    }
    max_num = i;
    tmp_sum = 0; i = vec.size() - 1; int j = 0;
        // 큰 것부터 더해보아서 필요한 조합의 최소 갯수 구하기
    while (tmp_sum <= K) {
        tmp_sum += vec[i--].first;
        j++;
    }
    min_num = j-1;

    // 갯수의 범위에서 조합 돌리기
    int max = 0;
    int size = vec.size();
    for (int i = min_num; i <= max_num; i++) {
        vector<int> combination(size, 0);
        int turn = i; int idx = size - 1;
        while (turn--) {
            // 뒤에서부터 1 채우기
            combination[idx--] = 1; 
        }
        do {
            int sum = 0; int value = 0;
            for (int i = 0; i < size; i++) {
                if (combination[i] == 1) {
                    sum += vec[i].first;
                    value += vec[i].second;
                }
                if (sum > K)
                    break;
            }
            if (sum > K)
                continue;
            max = max > value ? max : value;
        } while (next_permutation(combination.begin(), combination.end()));
    }

    cout << max << endl;
}

 

풀이

DP를 이용하는 방법을 생각하면서, 배열을 이용하여 구현할 수 있을 것 같다는 생각을 했는데 자세한 풀이가 생각나지 않아 그냥 지나쳐 버렸다.

https://yabmoons.tistory.com/571 에서 참고한 자세한 풀이는 이렇다.

이러한 배열의 형태로, 물건을 하나씩 보면서 해당 물건을 넣을지 말지 결정하는 것이다. 남은 weight가 해당 물건의 무게보다 크면 넣기로 하자.

만약 넣는다고 결정하면 현재 남은 weight에서 해당 물건의 weight를 뺀 값이 열 값이 될 것이고 다음 물건으로 넘어가게 될 것이다.

만약 넣지 않는다면 weight는 그대로하고 다음 물건으로 넘어가게 된다.

이러한 과정을 무게가 1일 때부터 K일 때까지로 가정한 상황에서 모두 이행해주면 모든 상황에서의 최대 value가 추출된다.