여행 짐 싸기

문제링크: 여행 짐 싸기

유명한 문제인데 풀 때마다 새롭다. 

이런 류의 문제들은 패턴이 있으니 기억하자.

배낭에 넣었을 때와 안넣을때의 값 중에 max를 취한다. 

일단 최대 절박도를 구하는 함수를 구하고, 그 함수를 이용하여 선택한 item들을 재구성한다. 

- recursive

무게가 capacity만큼 남았을 때, 해당 item부터 마지막 item들까지 넣었을 때 얻을 수 있는 최대절박도를 구하는 함수를 만든다.

 

#include <iostream>
#define max(a,b) (a)>(b)?(a):(b)
using namespace std;
int C, N, W;
typedef struct {
    char name[21];
    int volumn;
    int needs;
}Package;
const int MAXW = 1001;
const int MAXN = 101;
Package goods[MAXN];
int cache[MAXW][MAXN];
int Pick[MAXN];
int Top = 0;
 
// 최대 절박도를 return
int pack(int capacity, int item) {
    if (item == N)    return 0;
 
    int &ret = cache[capacity][item];
    if (ret != -1) return ret;
 
    ret = 0;
    // 현재 item을 선택x
    ret = pack(capacity, item + 1);
    // 현재 item을 선택했을 때 절박도를 비교하여 max값을 취함.
    if(capacity>=goods[item].volumn)
        ret = max(ret, pack(capacity-goods[item].volumn, item+1)+goods[item].needs);
    
    return ret;
}
 
 
// 담긴 물품
void reconstruct(int capacity, int item) {
    if (item == N)
        return;
    // item번째 절박도와 item+1번째 절박도가 같으면.. 즉, item을 안담은 것임
    if (pack(capacity, item) == pack(capacity, item + 1))
        reconstruct(capacity, item+1);
    else {
        Pick[Top++] = item;
        reconstruct(capacity-goods[item].volumn, item + 1);
    }
}
 
void printItems() {
    cout << Top << endl;
    for (int i = 0; i < Top; i++) {
        cout << goods[Pick[i]].name << endl;
    }
}
 
void init() {
    for (int i = 0; i < MAXW; i++)
        for (int j = 0; j < MAXN; j++)
            cache[i][j] = -1;
    Top = 0;
 
}
 
int main() {
    freopen("input.txt", "r", stdin);
    cin >> C;
    for (int c = 0; c < C; c++) {
        cin >> N >> W;
        for (int i = 0; i < N; i++) {
            cin >> goods[i].name >> goods[i].volumn
                >> goods[i].needs;
        }
        init();
        cout << pack(W, 0) << " ";
        reconstruct(W, 0);
        printItems();
 
    }
    return 0;
}

- iterative

pack 함수와 동일하게 2차원 배열을 이용하여 다시 구현해 보았다. 

iterative하게 생각하는 것은 쉽지 않다. ㅠ.ㅠ

pack[item][weight]

이전 item들을 선택했을 때의 절박도를 저장해두고,

weight을 증가시키면서 item의 weight보다 커졌을 때, 이 전 item들을 선택했을 때의 절박도에 현재 절박도를 비교해

max 값을 갱신하면서 전체 item과 무게를 모두 for loop으로 돌며 계산한다. 

item 추적

- N,W번째 절박도에서 전단계 item 선택으로 가면서 절박도가 달라질 때, 해당 item이 선택된 것이다. 

- 무게를 빼준 후 다시 비교한다.

 

#include <iostream>
#define max(a,b) (a)>(b)?(a):(b)
using namespace std;
int C, N, W;
typedef struct {
    char name[21];
    int volumn;
    int needs;
}Package;
const int MAXW = 1001;
const int MAXN = 101;
Package goods[MAXN];
int Pick[MAXN];
int Top = 0;
 
int Needs[MAXN][MAXW];
void pack2() {
    Needs[0][0] = 0;
    int maxV = 0;
    for (int item = 1; item <= N; item++) {
        for (int weight = 1; weight <= W; weight++) {
            // 현재 item을 넣지 않은 상태
            maxV = Needs[item - 1][weight];
            // 전단계 절박도에 현재 절박도를 더한 값이 전단계 절박도보다 크면 max값 갱신
            if (weight >= goods[item].volumn &&
                maxV < (Needs[item - 1][weight - goods[item].volumn] + goods[item].needs)) {
                maxV = Needs[item - 1][weight - goods[item].volumn] + goods[item].needs;
            }
            Needs[item][weight] = maxV;
 
        }
    }
}
 
void printItems() {
    int weight = W;
    int items[MAXN], index = 0;
    // 역으로 추적한다. 
    for (int i = N; i > 0; i--) {
        // 이전 선택과 현재 선택의 절박도가 다를 때까지 item 건너뜀
        if (Needs[i-1][weight] == Needs[i][weight])
            continue;
        items[index++] = i;                    // 선택된 item 저장
        weight = weight - goods[i].volumn;    
 
    }
    cout << index << endl;
    for(int i=0;i<index;i++)
        cout << goods[items[i]].name << " ";
    cout << endl;
}
 
int main() {
    freopen("input.txt", "r", stdin);
    cin >> C;
    for (int c = 0; c < C; c++) {
        cin >> N >> W;
        for (int i = 1; i <= N; i++) {
            cin >> goods[i].name >> goods[i].volumn
                >> goods[i].needs;
        }
 
        pack2();
        cout << Needs[N][W] << " ";
        printItems();
 
    }
    return 0;
}