[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