[Gold 5] 12865번 평범한 배낭

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

12865번: 평범한 배낭

 

이 문제는 DP를 통해 해결할 수 있다.

 

가방에 물건을 넣을 수 있는 조건은 아래와 같다.

• 현재 무게가 K이하면 계속해서 가방에 넣을 수 있다.

DP배열을 이용하여 1번째 물건부터 i번째 물건까지 담을 수 있는 가장 최대 가치를 저장한다.

 

예제의 주어진 입력으로 이차원배열 DP를 채워보면 아래와 같은 결과가 나온다.

4 7
6 13
4 8
3 6
5 12

	limit = 1	limit = 2	limit = 3	limit = 4	limit = 5	limit = 6	limit = 7
i = 1	0	0	0	0	0	13	13
i = 2	0	0	0	8	8	13	13
i = 3	0	0	6	8	8	13	14
i = 4	0	0	6	8	12	13	14

 

limit가 1인 경우, limit가 2인 경우

• 아무것도 담을 수 없다.

limit가 3인 경우

• W[3]은 무게가 3이기 때문에 담을 수 있다. V[3] = 6이므로, DP[3][3]을 6으로 채워준다. 
• W[4]는 5이기 때문에 네번째 물건은 담을 수 없다.
  • 그렇기 때문에 4번째 물건까지 고려하기 직전인 3번째 물건까지 고려했을 때 최대 가치인 DP[3][3]을 DP[4][3]에도 넣어주면 된다. 

limit = 4일 때

•  첫번째 물건을 고려했을 때, W[1] = 6이기 때문에 담을 수 없다. DP[1][4]에는 0을 채워준다.
• 두번째 물건까지 고려했을 때, W[2] = 4이기 때문에 담을 수 있다. DP[2][4]에는 두번째 물건의 가치 "V[2] = 8"을 채워준다.
• 세번째 물건까지 고려했을 때, W[3] = 3이기 때문에 담을 수 있다. 그런데 V[3] = 6이고, 이것은 두번째 물건을 고려했을 때, 즉 두번째 물건만 담았을 때보다 가치가 더 적기 때문에 DP[3][4]에는 DP[2][4]의 값을 그대로 넣어준다.
• 네번째 물건까지 고려했을 때, W[4] = 5이기 때문에 담을 수 없다. 그래서 세번째 물건까지 고려했을 때의 값인 DP[3][4]를 DP[4][4]에도 넣어준다. 

limit = 5일 때

•  첫번째 물건을 고려했을 때, W[1] = 6이기 때문에 담을 수 없다. DP[1][5]에는 0을 채워준다.
• 두번째 물건까지 고려했을 때, W[2] = 4이기 때문에 담을 수 있다. DP[2][5]에는 두번째 물건의 가치 "V[2] = 8"을 채워준다.
• 세번째 물건까지 고려했을 때, W[3] = 3이기 때문에 담을 수 있다. 그런데 V[3] = 6이고, 이것은 두번째 물건을 고려했을 때, 즉 두번째 물건만 담았을 때보다 가치가 더 적기 때문에 DP[3][5]에는 DP[2][5]의 값을 그대로 넣어준다.
• 네번째 물건까지 고려했을 때, W[4] = 5이기 때문에 담을 수 있다. V[4] = 12로, 이 값은 세번째 물건까지 고려했을 때 가치인 8보다 크기 때문에 DP[4][5]는 12로 채워준다. 

limit = 6일 때

•  첫번째 물건을 고려했을 때, W[1] = 6이기 때문에 담을 수 있다. DP[1][6]에는 V[1] = 13을 채워준다.
• 두번째 물건까지 고려했을 때, W[2] = 4이기 때문에 담을 수 있다. 그런데 V[2] =8이고, 이것은 첫번째 물건까지 고려했을 때, 즉 첫번째 물건만 담았을 때보다 가치가 더 적기 때문에 DP[2][6]에는 DP[1][6]의 값을 그대로 넣어준다.
• 세번째 물건까지 고려했을 때, W[3] = 3이기 때문에 담을 수 있다. 그런데 V[3] = 6이고, 이것은 두번째 물건까지 고려했을 때 보다 가치가 더 적기 때문에 DP[3][6]에는 DP[2][6]의 값을 그대로 넣어준다.
• 네번째 물건까지 고려했을 때, W[4] = 5이기 때문에 담을 수 있다. V[4] = 12로, 이 값은 세번째 물건까지 고려했을 때 가치인 13보다 작기 때문에 DP[4][6]는 DP[3][6]의 값을 그대로 채워준다. 

limit = 7일 때

•  첫번째 물건을 고려했을 때, W[1] = 6이기 때문에 담을 수 있다. DP[1][7]에는 V[1] = 13을 채워준다.
• 두번째 물건까지 고려했을 때, W[2] = 4이기 때문에 담을 수 있다. 그런데 V[2] =8이고, 이것은 첫번째 물건까지 고려했을 때, 즉 첫번째 물건만 담았을 때보다 가치가 더 적기 때문에 DP[2][7]에는 DP[1][7]의 값을 그대로 넣어준다.
• 세번째 물건까지 고려했을 때, W[3] = 3이기 때문에 담을 수 있다. 이때, 이전과는 다르게 한번 더 생각해야한다!!!
  • 왜냐하면 만약 무게가 3인 세번째 물건을 담으면, 백팩은 무게 4가 남게 된다.
  • 그 남은 무게에서 최대 가치는-> "limit=4이고 두번째 물건까지 고려했을 때"인 DP[2][4]가 된다.
  • 그리고 만약 무게가 3인 세번째 물건을 담지 않으면, 두번째 물건까지 고려했을 때의 최대 가치인 DP[2][7]의 값을 DP[3][7]에도 채워주면 된다. 

점화식으로 표현하면 다음과 같다.

 

DP[i][k] (최대 k무게까지 담을 수 있고, 1~i번째 물건까지 고려했을 때, 최대 가치 합) 

1) DP[i-1][k]                                                                                         (W[i] > k) : i번째 물건 무거워서 못 담을 때

2) max( DP[i - 1][k - W[i]]   +   V[i]  ,  DP[i-1][k] )                  (W[i] <=k and i>0) : i번째 물건 담았을 때

3) 0                                                                                                    (i = 0 and k = 0)       

           

#include<iostream>
#include <vector>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
int N, K;
int W[101] = {0,};
int V[101] = {0,};
int DP[101][100001];
 
void dp(){
    
    for(int limit = 1; limit<=K; limit++){
        for(int row = 1; row<=N; row++){
            //1. 담을 수 없을 경우
            if(W[row] > limit){
                DP[row][limit] = DP[row-1][limit];
            }
            //2. 담을 수 있는 경우
            else{
                DP[row][limit] = max(DP[row-1][limit - W[row]] + V[row]  ,  DP[row-1][limit]);
            }
        }
    }
    
}
 
int main(){
 
    cin >> N >> K;
    for(int i = 1; i<=N; i++){
        cin >> W[i] >> V[i];
    }
    
	//초기화
    for(int r=0; r<=N; r++)
    {
        DP[r][0] = 0;
    }
    for(int c = 0; c<=K; c++){
        DP[0][c] = 0;
    }
 
    dp();
 
    cout << DP[N][K];
    
    return 0;
}

 

 

https://nanyoungkim.tistory.com/182

[C++] 백준 12865번 - 평범한 배낭 (자세한 설명, DP, Knapsadck Problem)