[동적계획법 테크닉] 2. 여행 짐 싸기

컨셉

int packing(int index, int capacity)    //capacity만큼 용량이 남은 경우, item[index]부터 짐을 쌌을 때 가능한 최대 절박도를 리턴한다.

 

//packing(index,capacity) = item[index]를 짐에 넣은 경우, 안 넣은 경우 중 절박도가 큰 것

packing(index, capacity) = MAX(packing(index+1, capacity) , packing(index+1, capacity - items[index].volume);

 

초안

내가 쓴 코드(정답, 12ms)

/**
 * @name    9.2. 여행 짐 싸기
 * @ID      PACKING
 * @date    2019-08-16
 * @author  Sunmon
 */
 
#include <vector>
#include <algorithm>
#include <iostream>
#include <tuple>
#include <cstring>
 
#define VOLUME 0    //VOLUME, NEEDS, NAME; items[] index로 사용
#define NEEDS 1
#define NAME 2
 
using namespace std;
 
vector<string> bag;      //짐 싼 것 이름 저장
tuple<int, int, string> items[100]; //items<부피, 절박도, 이름>
int cache[100][1000+1];
int N, CAPACITY;
 
 
//capacity만큼 용량이 남았을 때, items[index]부터 짐을 쌌을 경우 최대 절박도의 합 리턴
int packing(int index, int capacity)
{
    //base case
    if(index == N) return 0;
    if(capacity < get<VOLUME>(items[index])) return 0;
 
    int& ret = cache[index][capacity];
    if(ret != -1) return ret;
 
    //짐을 싸는 경우 & 안 싸는 경우의 최댓값 리턴
    int untaken = packing(index+1, capacity);
    int taken = packing(index+1, capacity - get<VOLUME>(items[index])) + get<NEEDS>(items[index]);
 
    return ret = max(untaken, taken);
}
 
//가방에 넣은 아이템 이름을 bag에 저장한다
void reconstruct(int index, int capacity)
{
    if(index == N) return;
    if(packing(index, capacity) == packing(index+1, capacity)) reconstruct(index+1, capacity);
    else
    {
        bag.push_back(get<NAME>(items[index]));
        reconstruct(index+1, capacity - get<VOLUME>(items[index]));
    }
}
 
int main()
{
    int cases;
    cin >> cases;
    while(cases--)
    {
        memset(cache, -1, sizeof(cache));
        bag = {};
 
        //입력받기
        cin >> N >> CAPACITY;
        for(int i = 0; i<N; i++)
            cin >> get<NAME>(items[i]) >> get<VOLUME>(items[i]) >> get<NEEDS>(items[i]);
 
        //부피 오름차순으로 정렬
        sort(items, items+N);
        reconstruct(0, CAPACITY);
 
        cout << packing(0, CAPACITY) << " " << bag.size() << endl;
        for(auto& b: bag) cout << b << endl;
    }
}

 

주의

벡터

벡터 초기화하는 방법 알아두자. vector.clear는 완전한 초기화가 안 된다.

- vector.clear() ; 원소만 지움. 메모리 할당한 것은 그대로!

- 메모리까지 아예 초기화하는 방법; (vector<int> v)

    1. v = {};

    2. v = vector<int>();

    3. vector<int>().swap(v);

 

튜플(tuple)

데이터베이스의 그 튜플이 아니다. `pair`를 여러개로 늘인 것 == tuple

tuple에는 여러 쌍을 묶어서 저장할 수 있다.

 

- make_tuple(a, b, c);  //튜플 저장

- tie(a, b);    //튜플 저장. tie t(a,b) = tuple_temp; 이렇게 쓸수도 있다. temp꺼를 t에 저장하는것.

- get<index>(tuple_name); // 이 함수로 값을 읽어오기/ 저장하기 모두 처리 가능!

 

tie와 make_tuple의 차이점은 따로 포스팅 할 예정