[C++] BOJ 12865번 : 평범한 배낭

📝 문제

---

💻 실행 코드

// BOJ12865번 : 평범한 배낭
#include<iostream>
using namespace std;

int n, k; // n : 물품의 수 / k = 버틸 수 있는 무게
int arr[101][100001];
int w[101]; // 물건의 무게
int v[101]; // 물건의 가치

int main() {
    cin >> n >> k; // 물품수와 버틸 수 있는 무게 입력받음
    for(int i = 1; i <= n; i++){ // 무게와 가치를 각각 배열에 저장
        cin >> w[i] >> v[i];
    }

    for(int i = 1; i <= n; i++){ // 1 - n 개
        for(int j = 0; j <= k; j++){ // 0 - k kg
            if(j >= w[i]) // j가 무게보다 클 때
                // 배열에 그 전 i번째 배열, j에서 무게를 뺐을 때 그 배열 원소가 존재한다면 현재 가치를 더함
                // 둘 중에 더 큰 것을 현재 배열에 넣음
                arr[i][j] = max(arr[i - 1][j], arr[i - 1][j - w[i]] + v[i]);
            else
                // j가 무게보다 크지 않다면 그 전 배열 원소를 넣음
                arr[i][j] = arr[i - 1][j];
        }
    }
    // 이중 for 문이 끝나면 맨 마지막 배열을 출력
    cout << arr[n][k];
}

---

📚 문제 풀이

물건에는 각각의 가치가 부여되고 그 가치를 최대한으로 하면서 배낭에 물건을 집어넣어야 함
그렇지만 배낭에는 무게 제한이 있음, 각각 물건에도 무게가 주어짐

1 ~ n개의 물건을 탐색하면서 최대한 가치가 높아야 함, 하지만 무게 초과하면 X

👉 Knapsack 알고리즘을 사용하면 풀 수 있는 문제

먼저 주어진 물건들을 차례로 w[i], v[i] 배열에 집어넣음

• w[i] : i번째 물건의 무게
• v[i] : i번째 물건의 가치

그리고 2차원 배열 생성

• arr[i][j] : 물건의 개수만큼 i 존재, 배낭에 넣을 수 있는 최대 무게만큼 j 존재

👇 위 개념으로 요렇게 작성 가능

arr[i][j] = max(arr[i - 1][j], arr[i - 1][j - w[i]] + v[i]);

위 코드를 보며 배열을 작성해 보았음

i = 1일 때, j = 6이 될 때 저 코드가 실행이 됨 j >= w[i]
그대로 가치값 13이 들어가게 됨
그리고 j = 7이 되어도 13이 들어감

i = 2일 때, j = 4일 때 코드 실행, 그대로 가치값 8이 들어감
근데 j = 6이 되었을 때는 13이 8보다 크기 때문에 arr[2][6]에는 arr[2-1][6]인 13이 들어가게 됨

i = 3이 되었을 때 가치값 6이 들어가다가 8이 들어가게 되고 13이 들어가게 되는데 arr[3][7]에서 arr[3-1][7-3]해서 arr[2][4]가 나오게 되는데 여기 원소 값이 존재하기 때문에 v[3]과 더해져 14라는 값이 나오게 됨
13보다 크기 때문에 14라는 값이 들어감

i = 4가 되었을 때 12가 들어가고 13이 들어가게 되지만 결국 14가 가장 큰 값이기 때문에 arr[4][7]에 저장되고 arr[n][k]를 출력했을 때 14라는 가치 최댓값이 나오게 됨

---

✅ 실행 결과