[백준] 12865 : 평범한 배낭, 0/1 배낭문제

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

12865번: 평범한 배낭

 

배낭 문제(무게, 가치 고려)라 평범한 그리디 알고리즘이라고 생각했으나, 0/1 배낭문제이므로 dp이다.

0/1 배낭문제

각 아이템을 배낭에 넣거나(1) 넣지 않는(0) 둘 중 하나의 선택만 가능하다.

특징

1. 부분최적구조(그리디)가 아닌 dp 이다.

그리디 : 물건의 무게와 가치를 고려하여 현재 상황에서 가장 좋아보이도록 배낭에 물건을 넣는 것

하지만 위 문제의 경우 그리디 방법으로 풀면 최적해가 나오지 않는다.

즉, 물건의 모든 조합을 고려해야 최적해를 구할 수 있다.
      완전탐색+메모이제이션 가능 => dp

2. 물건을 여러번 넣을 수 없다. (중복X)

배낭의 최대 용량부터 아이템의 무게까지 역순으로 dp 배열을 채워나감으로써 물건이 중복되지 않도록 한다.

 

3. dp[i] = 배낭 용량이 i kg일때 담을 수 있는 물건들의 최대 가치

위 문제유형에서 dp 배열의 기준은 배낭의 무게이다.

물건들의 무게 합이 꼭 i가 되지 않아도 된다.

이유 : 물건마다 역순으로 배낭 최대 무게(용량)부터 물건의 무게까지 dp값을 계속해서 업데이트하기 때문이다.

 

이해가 안 갈 수 있으므로 chatgpt를 이용해 간단한 예시를 들고왔다. 업데이트 과정을 보면 된다.

배낭 문제 예시
예를 들어, 준서가 여행을 가기 위해 최대 8kg까지 담을 수 있는 배낭을 가지고 있다고 가정해 봅시다. 준서가 고를 수 있는 몇 가지 물건들과 그들의 무게와 가치는 다음과 같습니다:

물건 A: 무게 3kg, 가치 5
물건 B: 무게 2kg, 가치 3
물건 C: 무게 4kg, 가치 7
물건 D: 무게 5kg, 가치 9

 

목표
준서의 목표는 배낭의 무게 한도 8kg 내에서 물건들을 선택하여 가치의 합을 최대로 만드는 것입니다.

동적 프로그래밍 접근법
동적 프로그래밍을 사용하여 이 문제를 해결하기 위해, dp[i]를 "배낭의 용량이 ikg일 때 담을 수 있는 물건들의 최대 가치"로 정의합니다.
초기에 dp[0]부터 dp[8]까지 모두 0으로 설정합니다. 그 후, 각 물건에 대해 dp 배열을 업데이트합니다.

업데이트 과정
물건 A, B, C, D에 대해 각각 다음과 같이 dp 배열을 업데이트합니다:

물건 A (3kg, 5): 3kg부터 8kg까지의 dp 값을 업데이트합니다. 예를 들어, dp[3]는 5가 됩니다 (물건 A만 사용).
물건 B (2kg, 3): 2kg부터 8kg까지의 dp 값을 업데이트합니다. 예를 들어, dp[5]는 max(dp[5], dp[3] + 3)가 됩니다 (물건 A와 B를 조합).
물건 C (4kg, 7): 4kg부터 8kg까지의 dp 값을 업데이트합니다.
물건 D (5kg, 9): 5kg부터 8kg까지의 dp 값을 업데이트합니다.

 

결과
모든 업데이트가 완료된 후, dp[8]은 준서가 최대 8kg의 무게 제한 내에서 담을 수 있는 물건들의 최대 가치를 나타냅니다. 이 값은 준서가 배낭에 담을 수 있는 최적의 물건 조합을 반영합니다.

 

코드

#include <bits/stdc++.h>
using namespace std;
int n, k, w, v;
vector<pair<int, int>> product;
int dp[100004];
int main(){
    cin.tie(0); ios_base::sync_with_stdio(false); cout.tie(0);
    // 1. 입력받기
    cin >> n >> k;
    for(int i=0;i<n;i++){
        cin >> w >> v;
        product.push_back({w, v}); // 무게, 가치
    }
    
    // 3. dp 수행
    for(int i=0;i<n;i++){
        tie(w,v) = product[i];
        for(int j=k;j>=w;j--){
            dp[j] = max(dp[j], dp[j-w]+v);
        }
    }
    // 4. 정답 출력
    cout << dp[k];
}

 

java로 푸려고 했는데 c++과 자료구조도 다르고 함수도 달라서 적응의 시간이 필요할 것 같다.

1월부터 java 다시 공부하면서 풀 예정이다!

(역시 java 개발자는 java로 문제를 푸는것이 좋은 것 같다..)