[DP] 12865번 평범한 배낭

12865번 평범한 배낭

 

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

 

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K무게까지의 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

 

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

 

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

 

예제 입력

4 7
6 13
4 8
3 6
5 12

 

예제 출력

14

 

해결방법

knapsack 을 적용한 DP 문제이다

 

 

⭐️ 솔루션 ⭐️

N : 물건의 개수 (≤ 100)

K : 가방의 한계 (≤ 100,000)

D(i, k) : i 번째 물건까지 사용하여 k 용량의 가방에 물건을 채울 때의 최대 가치

W[i] : i 번째 물건의 무게 (≤ 100,000)

V[i] : i 번째 물건의 가치 (≤ 1,000)

 

처음 점화식을 세운 뒤, 제출을 했을 때 틀렸습니다 가 나왔다

그래서 백준 사이트에 질문을 올렸는데 아래와 같은 답변을 받았다

1 2
1 1

답은 1입니다. 지금 코드는 한 물건을 여러 번씩 쓰고 있습니다.

호옹이....!!!

답변을 바탕으로 점화식을 수정했다

 

 

[ 초기 점화식 ]

D(i,k) =  { D(i-1,k) (W[i] > k)
    	  { max(D(i-1,k), D(i,k-W[i] + V[i] (W[i] ≤ k))

[ 수정한 점화식 ]

D(i,k) =  { D(i-1,k) (W[i] > k)
    	  { max(D(i-1,k), D(i-1,k-W[i] + V[i] (W[i] ≤ k))

 

위의 두 점화식을 보면 작은 차이점이 존재한다

먼저 물건의 무게가 현재 가방의 용량보다 클 때는 기존의 최대 가치를 유지하는 것은 동일하다

물건의 무게가 현재 가방의 용량보다 작거나 같을 때는 현재 가방에 i 번째 물건을 넣을 수 있는 경우, i 번째 물건을 선택하지 않는 경우 vs i 번째 물건을 선택하는 경우 를 비교한다

이 때, D[i,k-W(i) D[i-1,k-W(i) 은 어떤 차이가 있을까??

전자의 경우는 1 ~ i 번째의 경우에서 값을 가져오기 때문에 물건을 여러번 선택하게 된다

후자의 경우는 1 ~ i-1 번째의 경우에서 값을 가져오기 때문에 물건을 한번만 선택하게 된다

 

이를 구현하기 위해 가방의 용량을 1 ~ k 가 아닌 k ~ 1 로 거꾸로 접근하여 문제를 해결하였다

 

 

 

소스코드

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;

int n,k;
int d[100001];  // 가방 용량
int w[101];     // 물건의 무게
int v[101];     // 물건의 가치

void dp(){
    for(int i=1; i<=n; i++){
        for(int j=k; j>=1; j--){
            if(w[i] <= j){
                d[j] = max(d[j], d[j-w[i]] + v[i]);
            }
        }
    }
    
    cout << d[k] << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin >> w[i] >> v[i];
    }
    
    dp();
    
    return 0;
}