Knapsack 알고리즘 (백준 12865번 - 평범한 배낭)

배낭 문제 라고 불리는 유형들이 있다.
그 문제와 이 문제를 푸는 알고리즘에 대해서 알아보자!

문제

문제 출처 : 백준 12865번 - 평범한 배낭

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

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

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

아이디어

이 문제를 어떻게 풀까 생각해보자.

먼저, 각 물건에 대해서 우리가 선택할 수 있는 선택지는 2개이다. 담거나, 담지 않거나.
근데 이 선택지는 마지막에 판단해야 할 문제고, 가장 중요한 것은 무엇일까?

마지막에 고른 물건과, 배낭에 남아 있는 용량이다.

그럼 우리는 부분 문제를 만들 수 있다.

Pack(capacity, itemnumber) : 캐리어에 Capacity 만큼 용량이 남았을 때, itemnumber 이후의 물건들을 싸서 얻을 수 있는 가치의 최댓값.

그리고 아까 생각했던, 물건을 담거나 담지 않거나 이 두 경우로 분류한다.
(weight[i], value[i] : i 번째 물건의 무게와 가치)

1. 담지 않을 경우 : Pack(capacity,itemnumber + 1)

2. 담은 경우(이 때, capacity >= weight[item] 이어야 하는 것은 당연하다.) : Pack(capacity - weight[item], itemnumber + 1) + value[item]
   아이템을 담았으니까 남은 용량에서 담은 아이템의 무게를 빼주고, pack 함수는 가치를 반환하니까 담은 아이템의 가치를 더해줘야 한다.

그래서 이 두가지 경우 중 최댓값을 반환하면 된다.

풀이 코드

다른 코드보다 pack(int w, int number) 함수를 유심히 보면 된다.

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int n,k;    // n : 물품의 수, k : 버틸 수 있는 무게.
int item[100];
int weight[100];
int value[100001][100];

int pack(int w, int number){
    if (number == n)  // 더 담을 물건이 없넹? 물건 번호가 0부터 n-1까지니까.
        return 0;
    int &ret = value[w][number];
    if(ret != - 1)
        return ret;

    ret = pack(w,number+1);     // 담지 않는 경우.
    if(w >= weight[number])	// 물건이 배낭에 들어갈 수 있을 때 담아야 한다.
        ret = max(ret, pack(w-weight[number], number+1) + item[number]);	// 담지 않는 경우와 담는 경우 중 큰 값은?

    return ret;

}
int main(){
    cin >> n >> k;
    int w,v;
    memset(value,-1,sizeof(value));
    for(int i = 0; i < n; i++){
        cin >> w >> v;
        weight[i] = w;
        item[i] = v;
    }

    pack(k,0);
    cout << value[k][0];
    return 0;
}

LIS 알고리즘보단 훨씬 쉬운 듯 하다.