[C++] 여행 짐 싸기 (동적계획법)

https://algospot.com/judge/problem/read/PACKING

소요 시간: 1시간 25분 +

해결: X

Knapsack 자체는 해결했지만 경로복구에서 막혀서 교재를 참고했습니다.

---

풀이

Knapsack 알고리즘을 배운 적이 있어서 DP 풀이가 바로 떠올랐습니다.

식은 아래와 같습니다.

i는 물건의 번호, c는 가방의 최대 용량, v는 물건의 부피, d는 물건의 절박도 입니다.

 

 

경로 복원에 익숙하지 않아서 물건 i에 대한 (서로 다른 c에 대한) 여러 부분 문제 중

어떤게 유효한 건지 확인하는 방법을 계속 생각했어요.

 

결국 이 부분에서 책을 참고했습니다.

분제를 분할하면서는 당연히 같은 물건에 대해 여러 부분 문제를 계산할 수 밖에 없으니,

계산을 미리 해놓고 계산 결과를 따라가며 경로를 찾아야 했습니다...!

 

그렇다면 계산 결과를 따라가는 조건이 뭘까요.

L[i,v]가 L[i+1,v]와 같으면 i번째 물건을 고르지 않았다는 의미이고,

같지 않다면 i번째 물건을 골랐다는 의미입니다.

 

이를 재귀적으로 n번째 물건까지 검사하면 물건의 개수와 목록을 얻을 수 있죠.

---

코드

typedef struct{
    string name;
    int volume;
    int weight;
} Item;

int n, w;
Item items[101];
int cache[101][1001];
bool route[101];

int put(int num, int vol){
    if(num==n) return 0;
    
    int& ret = cache[num][vol];
    if(ret!=-1)return ret;
    
    Item cur = items[num];
    ret = put(num+1, vol);
    if(vol>=cur.volume)
        ret = max(ret, put(num+1, vol-cur.volume) + cur.weight);
    
    return ret;
}

void trace_route(int num, int vol, vector<string>& picked){
    if(num==n)return;
    
    if(put(num,vol) == put(num+1, vol)){
        trace_route(num+1, vol, picked);
    }
    else{
        trace_route(num+1, vol-items[num].volume, picked);
        picked.push_back(items[num].name);
    }
}

---

스터디

해당 문제는 최대 무게가 1000, 물건의 개수가 100개로 메모이제이션에 충분한 크기이지만

훨씬 커지면 메모이제이션을 적용할 수 없다고 합니다.

 

그런 문제가 바로 아래

https://www.acmicpc.net/problem/7579

 

가중치/부피로 메모이제이션을 하면 된다고 해요.