문제링크 입니다

[PACKING] 문제 😭😭😭😭😭

여행을 떠나기 전날까지 절대 짐을 싸지 않는 버릇이 있는 재훈이는 오늘도 비행기 타기 전날에야 가방을 싸기 위해 자리에 앉았습니다. 비행기 규정상 재훈이는 캐리어를 하나만 가지고 갈 수 있는데, 아무래도 가져가고 싶은 물건들이 캐리어 안에 다 들어가지 않을 것 같습니다. 재훈이는 가져가고 싶은 각 물건들의 부피와 얼마나 필요한지를 나타내는 절박도를 조사해 다음과 같은 목록을 만들었습니다.

PACKING
PACKING

캐리어의 용량이 정해져 있기 때문에 가져갈 수 있는 물건들의 부피 합은 캐리어의 용량 w 이하여야 합니다. 이때 절박도를 최대화할 수 있는 물건들의 목록을 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1≤C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 가져가고 싶은 물건의 수 N (1≤N≤100)과 캐리어의 용량 W (1≤W≤1000)가 주어집니다. 그 이후 N줄에 순서대로 각 물건의 정보가 주어집니다. 한 물건에 대한 정보는 물건의 이름, 부피, 절박도 순서대로 주어지며, 이름은 공백 없는 알파벳 대소문자 1글자 이상 20글자 이하의 문자열, 부피와 절박도는 1000 이하의 자연수입니다.

출력

각 테스트 케이스별 출력의 첫 줄에는 가져갈 수 있는 물건들의 최대 절박도 합과 가져갈 물건들의 개수를 출력합니다. 이후 한 줄에 하나씩 각 물건들의 이름을 출력합니다. 만약 절박도를 최대화하는 물건들의 조합이 여럿일 경우 아무 것이나 출력해도 좋습니다.

입력 예제

2
6 10
laptop 4 7
camera 2 10
xbox 6 6
grinder 4 7
dumbell 2 5
encyclopedia 10 4
6 17
laptop 4 7
camera 2 10
xbox 6 6
grinder 4 7
dumbell 2 5
encyclopedia 10 4

출력 예제

24 3
laptop
camera
grinder
30 4
laptop
camera
xbox
grinder

전체 코드는 다음과 같습니다.

//
//  PACKING.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/09/30.
//

#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
#include <vector>
#include <tuple>
using namespace std;

int N; // 가지고싶은 물건의 수
int W; // 캐리어의 용량
vector<tuple<string,int,int>>vec;
vector<string> answer;
int answer_count;
int answer_precious;
int cache[1001][101];

ifstream fin("PACKING.txt");
int packing(int, int);

void solve_answer(int capacity, int item){
    if(item == N) return;
    //  안담앗을때 같음.
    if(packing(capacity,item) == packing(capacity, item+1)){
        solve_answer(capacity, item+1);
    }
    else{ // 담았을때..
        answer.push_back(get<0>(vec[item]));
        answer_count++;
        answer_precious += get<2>(vec[item]);
        solve_answer(capacity - get<1>(vec[item]), item +1);
    }
}
int packing(int capacity, int item){
    // 기저 사례
    if(item == N) return 0;
    int& ret = cache[capacity][item];
    if(ret != -1) return ret;

    //물건 안담을 경우
    ret = packing(capacity, item +1);
    //물건 담을 경우
    if(capacity >= get<1>(vec[item])){
        ret = max(ret, packing(capacity-get<1>(vec[item]), item+1) + get<2>(vec[item]));
    }
    return ret;
}

int main(int argc, const char * argv[]) {
    int Test_case;
    fin >> Test_case;
    for (int i=0; i < Test_case ; i++){
        fin >> N;
        fin >> W;
        vec.clear();
        answer.clear();
        answer_count =0;
        answer_precious =0;
        memset(cache, -1, sizeof(cache));
        for(int i=0; i <N; i++){
            string str;
            int volume;
            int precious;
            fin >> str;
            fin >> volume;
            fin >> precious;
            vec.push_back(make_tuple(str,volume,precious));
        }
        solve_answer(W, 0);
        cout << answer_precious << " " << answer_count << endl;
        for(int i=0; i< answer.size(); i++){
            cout << answer[i] << endl;
        }
    }

    return 0;
}

Comments