[알고스팟] 여행 짐 싸기

문제 링크

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • PACKING
  • 2000ms
  • 65536kb
  • 4194
  • 1145 (27%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

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

물건	노트북 컴퓨터	카메라	XBOX365	커피그라인더	아령	백과사전
부피	4	2	6	4	2	10
절박도	7	10	6	7	5	4

캐리어의 용량이 정해져 있기 때문에 가져갈 수 있는 물건들의 부피 합은 캐리어의 용량 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

어떻게 풀까?

해당 문제는 절박도의 최대를 구해야 할 뿐만 아니라 최대의 절박도에서 경로까지 출력을 해야하는 문제입니다.

이러한 문제는 최적화에 대한 저장을 하는 배열뿐만 아니라 각 단계별로 선택한 최적해를 어떻게 출력할지 결정해주는 재귀 함수를 한번 더 구현하는 방법이 많이 쓰입니다.

위 문제는 어떻게해서 최적화 문제의 답을 구할 수 있을까요?

우선, 이름을 출력하는 부분을 제외하고 절박도의 최대를 고르는 측면만 생각해봅시다.

한 경우에서 나올 수 있는 경우의 수는 2가지 입니다.

첫 번째는 맨 처음 아이템을 선택 했을 경우입니다.

두 번째는 맨 처음 아이템을 선택하지 않을 경우입니다.

그리고 두 가지 경우에서 차이가 나는 부분은 '남은 배낭의 여분'입니다.

따라서 해당 문제는 남은 배낭의 여분과 현재 남아있는 아이템의 시작점에 따라서 최적해가 결정된다고 볼 수 있습니다.

그림을 통해 확인해 봅시다.

우선 데이터들을 위와 같이 저장하는 배열들입니다.

위 그림에서 보듯이, 한 물건 집합에서의 최대 절박도는 두 가지의 경우 중에서 최댓값을 선택하면 되는 문제로 나눌 수 있습니다.

우선, 해당 집합에서의 첫 번째 아이템을 선택하지 않은 경우입니다.

해당 집합에서의 첫 번째 아이템을 선택하지 않는다면, 바로 다음 부분 집합으로 넘어가서 현재의 최대 부피와 동일한 최대 부피를 채우는 문제에서의 최대 절박도를 구합니다.

다음은, 해당 집합에서의 첫 번째 아이템을 선택한 경우입니다.

해당 집합에서의 첫 번째 아이템을 선택하면, 그 다음 물건들의 부분집합으로 이루어진 집합들과 첫번째 아이템의 부피를 뺀 만큼의 부피를 전체 부피로 하는 경우의 절박도를 구합니다. 그리고 해당 아이템의 첫번째의 절박도를 더한 것이 바로 해당 물건을 선택했을때의 최대 절박도가 됩니다.

이 두가지 경우 중에서 더 높은 값이 바로 해당 집합에서 주어진 배낭 부피만큼 물건을 가져갈 수 있을 때 얻을 수 있는 최대 절박도입니다.

하지만, 결국 구해야하는 것은 해당 아이템들의 목록입니다. 이는 어떻게 구할 수 있을까요?

한 부분 집합이 주어 졌을 때, 해당 부분 집합들의 가장 앞에 있는 아이템의 번호가 부분집합의 대표가 되게하고, 

선택한 아이템들의 무게를 '무게'보다 넘지 않게 최대 절박도를 구하는 것을 pack(번호, 무게)라고 합시다.

그러면, 위 그림과 같이 pack(번호, 무게)와 pack(번호 + 1, 무게)로 나눌 수 있을 것 입니다.

만약 pack(번호, 무게)와 pack(번호 + 1, 무게)가 같다면 결국 해당 번호의 물건은 최대 절박도를 구하는데에 큰 의미가 없다는 것이 됩니다.

반대로 다르다면, 이는 첫 번째 물건이 최대 절박도를 구하는 데에 필요하다는 것이 됩니다.

따라서, 두 개의 값이 다르다면 해당 번호의 아이템을 결과 출력에 포함시키고, 반대의 경우는 무시하도록 재귀 함수를 만들면 됩니다. 

코드는 아래와 같습니다.

void setRes(int start, int v)
{
    if (start > n)
    {
        return;
    }
 
    if (choose2(start, v) == choose2(start + 1, v))
    {
        setRes(start + 1, v);
    }
 
    else
    {
        res[rLen++] = names[start];
        setRes(start + 1, v + info[start][V]);
    }
}

만약 다르다면 무게를 더해줘서 setRes(start + 1, v + 물건의 부피)를 확인한다는 것에 유의합시다!

코드

#pragma once
#include<cstdio>
#include<cstring>
 
int cache[101][1001];
char names[101][21];
int n, w;
int info[101][2];
 
char* res[100]; int rLen;
 
enum DATA  { V,W };
 
int getMax(int i1, int i2)
{
    return i1 < i2 ? i2 : i1;
}
 
int choose2(int now, int v)
{
    if (now > n)
    {
        return 0;
    }
 
    int& ret = cache[now][v];
    
    if (ret != -1) return ret;
 
    ret = choose2(now + 1, v);
    if( v + info [now][V] <= w)
        ret = getMax(ret, info[now][W] + choose2(now + 1, v + info[now][V]));
 
    return ret;
}
 
void setRes(int start, int v)
{
    if (start > n)
    {
        return;
    }
 
    if (choose2(start, v) == choose2(start + 1, v))
    {
        setRes(start + 1, v);
    }
 
    else
    {
        res[rLen++] = names[start];
        setRes(start + 1, v + info[start][V]);
    }
}
 
int main()
{
    int t;
    scanf("%d\n", &t);
 
    while (t--)
    {
        scanf("%d %d\n", &n, &w);
        memset(cache, -1, sizeof(cache));
 
        for (int i = 1; i <= n; i++)
        {
            scanf("%s %d %d\n", names[i], &info[i][V], &info[i][W]);
        }
 
        int maxW = choose2(0, 0);
        rLen = 0;
        setRes(0, 0);
 
        int idx = 0;
        printf("%d %d\n", maxW, rLen);
 
        for (int i = 0; i < rLen; i++) printf("%s\n", res[i]);
    }
    return 0;
}