[baekjoon] 12865번 : 평범한 배낭 (C++)

문제가 이해가 안돼서 한 5번정도 읽음

그니까 대충... 이해가 됐음!! 

일단 물건에는 각각의 가치가 부여가 되고 그 가치를 최대한으로 하면서 배낭에 물건을 집어넣어야 함

그렇지만 배낭에는 무게 제한이 있음... 물론 각각 물건에도 무게가 주어짐

 

[풀이]

그러니까 1 ~ n 개의 물건을 탐색 하면서 최대한 가치가 높아야 함 근데 또 무게가 초과가 되면 안됨

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라는 가치 최댓값이 나오게 됨

 

[전체코드]

// 12865_평범한 배낭
#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];
}