[동적 계획법] PACKING 여행짐 싸기

#include <iostream>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
 
class pac
{
public:
    std::string name;
    int imminence;
    int w;
    pac();
    pac(std::string na, int w1, int im);
    void printPac();
};
pac::pac()
{
    name = "";
    imminence = 0;
    w = 0;
}
pac::pac(std::string na, int w1, int im)
{
    name = na;
    imminence = im;
    w = w1;
}
void pac::printPac()
{
    std::cout<<name<<std::endl;
}
 
pac items[101];
int cache[1001][101];
int tracking[1001][101];
 
int packing(int remainW, int start)
{
    int &ret = cache[remainW][start];
 
    if(ret != -1)
        return ret;
 
    ret = 0;
    for(int next = start - 1; next >= 0; next--)
    {
        if(remainW >= items[next].w)
        {
            int cand = items[next].imminence + packing(remainW - items[next].w, next);
            if(ret <= cand ) 
            {
                ret = cand;
                tracking[remainW][start] = next;
            }
        }
    }
    return ret;
 
}
 
void printMaxItems(int remainW, int itemN, int count)
{
    if(tracking[remainW][itemN] == -1)
    {
        std::cout<<count<<std::endl;
        return;
    }
    else
    {
        printMaxItems(remainW - items[tracking[remainW][itemN]].w , tracking[remainW][itemN], count + 1);
        items[tracking[remainW][itemN]].printPac();
    }
    
}
 
int main()
{
    int testCase = 0, itemN = 0, w = 0, itemW = 0, itemI = 0;
    std::string na = {""};
    std::cin>>testCase;
    for(int i = 0; i < testCase; i++)
    {
        memset(cache, -1, sizeof cache);
        memset(tracking, -1, sizeof tracking);
        std::cin>>itemN>>w;
        for(int j = 0; j < itemN; j++)
        {
            std::cin>>na>>itemW>>itemI;
            items[j] = pac(na, itemW, itemI);
        }
        std::cout<<packing(w, itemN)<<" ";
        printMaxItems(w, itemN, 0);
    }
}

1. 메모이제이션

 

packing(w, n) = w만큼의 용량이 남았을 때 n번 물건 이후 물건들을 싸서 얻을 수 있는 최대 절박도

 

cache[w][n] = w만큼의 용량이 남았고, 이전에 n번을 택한상태에서의 최대 절박도.

 

2. 답 추적하기

 

답을 추적하려면 따로 최대값이 나올때의 경우를 저장해야한다.

 

tracking[w][n] = w만큼의 용량이 남았고, 이전에 n번을 택한 상태에서 다음 택하는 번호를 저장.

 

3. 시간 복잡도 분석

 

위 알고리즘 은 for문을 써서 모든 경우의 수를 구했으므로

부분문제의 풀이는 n 시간이 걸린다.

 

부분문제의 수는  함수의 인수로 오는 값의 두 곱인 

n * w 이다.

 

따라서 위 코드는 O(n^2 w) 이다.

 

책에서는 for문을 사용하지않고 

부분문제를 해당 물건을 가져가는 경우,

가져가지 않는 경우 로 분할하였고

별도의 계산이 없으므로

상수 시간안에 부분문제는 해결되어진다.

 

부분문제의 수는 같으므로

 

책의 코드는 O(n^2)이다.

 

 

A: 책의 함수 실행 횟수 B: 위의 함수 실행횟수

 

AA:  A - 메모이제이션  B: B - 메모이제이션 

 

의 함수 호출을 보면 차이가 많이나는것을 볼 수 있고,

부분문제의 개수에 따른 기저사례 차이 도 볼 수 있다.

 

n = 50, w = 1000

n = 37 , w = 240

n = 25, w = 500

n = 100, w = 1000

4. 반성

처음에 답을 추적하려고  tracking[n]이라는 배열을 만들었다. 

 

이는 tracking이 w에 종속되어 있다는것을 무시하는 것이며 

어느 순간에서 최대값인지 기억을 못하고

이상한 좌표로 업데이트됬을 수 있는 값을 리턴한다.

 

항상 메모이제이션을 할때 결과값이 어느 변수에 종속되어있는지

즉, 어떤 정보에 의해 답이 좌우되는지 파악하자.

 

또 이런 경우의 수를 세는 문제일 경우 for문을 줄이자

 

5. 책에서의 답 추적

책에서는 부분문제를 두개로 나누었다.

이로 인해 따로 선택을 저장하지 않고 답을 추적할 수 있는데

 

앞의 문제의 결과값과 뒤의 문제의 결과값이 같으면

뒤의 문제와 상관없이 최대값을 얻을 수 있다는 뜻이므로

추적을 쉽게 할 수 있다.

 

 

 

-알고리즘 문제해결전략 284p

PACKING