[C/C++] 백준 7579: 앱 (Kanpsack-DP)

7579: 앱

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

7579번: 앱

 

이 문제도 무게(weight)와 가치(value)이 존재하는 전형적인 배낭(Knapsack) 문제이다. 배낭 문제를 해결하는 방법은 용량/비용을 이용하여 backtracking을 하는 방법도 있지만 가장 널리 쓰이고 구현하기 쉬운 Dynamic Programming이 대표적이다. 이 문제 역시 Dynamic Programming을 이용하여 문제를 해결했다. 

 

 

Kanpsack 알고리즘!

 배낭 문제를 DP로 푸는 이유는 다음과 같다. 먼저 각 item을, 이 문제에서는 앱의 실행을 하는 여부에 따라 item의 개수가 n개라면 가장 무식하게 풀 경우(Bruteforce) 시간복잡도가 O(2^n)이 된다. 사실상 시간내에 절대 풀 수 없게 된다.

 

 또 다르게는 무게당 가치 순으로 제일 높은 item 부터 넣는 방법이 있는데 (Greedy) 이는 최적의 답을 도출해내지 못한다. Greedy 알고리즘은 사실상 정해져있는 경우가 많기 때문에 이를 먼저 배우는 것이 중요하다. 다만 Knapsack 문제 중에서도 Fractional Kanpsack (분할 가능한 배낭 문제)일때는 가능하고 0-1 Knapscak에서는 불가능하다. 이때 Fractional 문제는 item을 자를 수 있을 경우로 이 같은 경우에는 Greedy로 풀 수 있고 0-1은 자를 수 없는 문제로 Greedy로 해결 불가능하다. 자세한 설명은 아래 포스팅을 참고하면 된다. 

https://hi-guten-tag.tistory.com/160

[알고리즘 - 이론] 0-1 KnapSack Problem and Fractional KnapSack Problem (0-1 배낭 문제, 분할 가능한 배낭 문제)

 결국 이 문제는 DP를 이용하는데 큰 문제를 작은 문제로 쪼개서 해결하되 반복되는 연산을 막기 위해 메모리에 저장하여 반복 작업을 줄인다. 가장 기본적인 생각은 다음과 같다. 먼저 값들을 저장할 이차원 배열을 만든다. 이때 이 배열의 들어갈 각 수를 F(i,j)라고 할 때 이 배열에 들어갈 점화식은 밑과 같다. F(i,j)가 가장 최적의 답이고 n개의 item들의 무게가 w1,w2,...,wn이고 가치가 v1,v2...,vn이며 현재 capacity는 j, i는 item의 순서를 말한다.

 

1.  현재 남은 용량(capacity)에 i번째 item을 넣을 수 없는 경우 (j-wi<0)

 i번째 item은 넣지 못하고 i-1번째에서 가치(value)가 곧 i번째에서 최적의 답이 된다. (F(i,j)=F(i-j))

 

2. 현재 남은 용량(capacity)에 i번째 item을 넣을 수 있는 경우 (j-wi>=0)

 이 경우2-1) i번째 item을 선택하지 않을 때의 가치(value)와 2-2) i번째 item을 선택해 i번째 item의 무게(weigh)를 뺀 곳에서의 가치와 i번째 item을 더하여 둘 중에 (2-1, 2-2) 큰 값이 곧 최적의 답이 된다.

F(i,j)=max[F(i-1,j), vi+ F(i-1,j-wi)]

 

Kanpsack과 관련된 기본 문제는 아래 포스팅을 참고하면 된다

https://donggul-godsang.tistory.com/24

[C] 12865: 평범한 배낭

 

 

풀이!

이 문제도 마찬가지로 위와 같은 방법으로 문제를 해결하면 된다. 이 문제에서 x축은 앱 비활성화의 드는 비용, y축은 앱의 수로 기록한다. 이때 표를 다 채운 후 가장 먼저 M바이트 이상을 확보한 값이 저장되어 있는 곳의 x값(앱 비활성화의 최소 비용)을 출력하면 답이 된다. 

 dp[]배열에 저장하는 값을 한 문장으로 요약하면 같은 앱 비활성화의 비용으로 최대의 메모리를 구한 값이다. 

 이 문제에서 점화식의 코드는 다음과 같다

for(int j=1;j<=n;j++){
     for(int i=0;i<=add_byte;i++){
       int tmp=i-off[j];
       if(tmp<0){
         dp[j][i]=dp[j-1][i];
         continue;
       }
       dp[j][i]=max(dp[j-1][tmp]+byteb[j],dp[j-1][i]);
     }
   }

  예제에 있는 문제를 예시로 dp 배열을 채워보면

	0	1	2	3	4	5	6	7	8
dp[1]	0	0	0	30	30	30	30	30	30
dp[2]	10	10	10	40	40	40	40	40	40
dp[3]	10	10	10	40	40	40	60	60	60
dp[4]	10	10	10	40	40	45	60	60	75
dp[5]	10	10	10	40	50	50	60	80	80

이와 같이 나타나진다. 초록색은 1.현재 남은 용량에 item을 넣지 못한 경우 (tmp<0), 빨간색은 2. 현재 남은 용량에 item을 넣는 경우 , 검정색은 현재 남은 용량에 item을 넣을 수는 있지만 넣지 않는 것이 더 이득인 경우이다. 마지막으로 파란색은 답이 되는 값이다.

 

 

소스코드!

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<map>
#include<cstdlib>
#include<iomanip>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
int byteb[101];
int off[101];

int visit_once[101];

int dp[101][10001];

int main() {    
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,m,add_byte=0;
  cin>>n>>m;
  for(int i=1;i<=n;i++)
    cin>>byteb[i];
  for(int i=1;i<=n;i++){
    cin>>off[i];
    add_byte+=off[i];
  }
    

 for(int j=1;j<=n;j++){
     for(int i=0;i<=add_byte;i++){
       int tmp=i-off[j];
       if(tmp<0){
         dp[j][i]=dp[j-1][i];
         continue;
       }
       dp[j][i]=max(dp[j-1][tmp]+byteb[j],dp[j-1][i]);
     }
   }
  
  int ans;
  for(int i=1;i<=add_byte;i++){    
      if(dp[n][i]>=m){
        ans=i;
        cout<<ans;
        return 0;
      }  
  }  

}