[알고스팟] PACKING - 여행 짐 싸기 (C++, Knapsack)

문제

 

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

algospot.com :: PACKING

 

풀이

 

종만북 난이도: 중

 

일반적인 배낭 문제(Knapsack)에서 추가적으로 어떤 물건을 선택했는지까지 출력해야 하는 문제이다.

 

배낭 문제는 DP의 대표적인 문제로, 구현 방법에는 재귀 함수를 통해 큰 문제에서 작은 문제로 내려가며 해결하는 Top-Down 방식과 작은 문제에서부터 차례로 답을 찾아 올라가는 Bottom-Up방식이 있다.

 

이번 문제는 Bottom-Up 방식으로 해결하였다.

Bottom-Up 방식의 구현은 다음을 참고하자.

[백준] No.12865 - 평범한 배낭 (C++, 배낭 문제)

 

간단히 정리해 보면 idx번째 물건을 선택하거나 선택하지 않는 경우로 분기한다.

 

1. 선택하는 경우: dp[weight - idx.무게][idx-1] + idx.가치

선택한 무게만큼 현재 무게에서 빼주고 가치는 더해준다.

 

2. 선택하지 않는 경우: dp[weight][idx-1]

선택하지 않고 가치도 더해주지 않는다.

 

이 두 값 중 더 큰 값이 dp[weight][idx]의 값이 된다.

 

 

 

메모이제이션에 사용하는 dp[weight][item_idx]는 weight의 용량이 남았을 때 1번 ~ item_idx번까지의 물건으로 만들 수 있는 최대 가치(절박도)를 저장하게 된다.

이를 이용하면 재귀 함수로 최대 가치를 위해 선택해야 하는 물건을 찾을 수 있다.

 

 

답을 역추적하는 재귀 함수 Reconstruct

int total_value =0;
 
void Reconstruct(int capacity, int item_idx, vector<string>& answer_list){
  //끝에 도달한 경우
  if(item_idx == 0 || capacity <=0)
    return;
 
  // 같은 경우 item_idx는 선택하지 않는 것이 최대 가치를 만들 수 있음
  if(dp[capacity][item_idx] == dp[capacity][item_idx -1])
    Reconstruct(capacity, item_idx-1, answer_list);
  else{
    answer_list.push_back(item_list[item_idx].name); 
    //전체 절박도 합에 추가해주자.
    total_value += item_list[item_idx].value;
    Reconstruct(capacity - item_list[item_idx].weight, item_idx-1 , answer_list);
  }
}

 

dp[capacity][item_idx]는 해당 capacity에서 1~item_idx번 물건들로 만들 수 있는 가치의 최대 합이,

dp[capacity][item_idx -1]에는 capacity에서 1~item_idx-1번 물건들로 만들 수 있는 가치의 최대 합이 저장되어 있다.

 

따라서 dp[capacity][item_idx]과 dp[capacity][item_idx-1]값이 같다면

item_idx번째 물건은 가치를 최대로 만드는 물건들 중에 선택되지 않았음을 의미한다.

 

만약 두 값이 같지 않다면 dp[capacity][item_idx]값이 더 크다는 것을 의미한다.

그 이유는 dp[capacity][item_idx-1]는 가치를 최대로 만들 때 item_idx 번째 물건을 포함시킬 수 없기 때문에 dp[capacity][item_idx ]보다 같거나 작을 수밖에 없다.

따라서 두 값이 같지 않은 경우 item_idx번째 물건은 답에 포함이 되므로 배열에 저장해 두자.

 

 

 

코드