0/1 냅색 문제 풀이하기

끄적인 필기

간단하게 끄적인 노트

설명

 가방 문제라고도 하는 이 알고리즘은 일정한 Capacity가 있고 이 Capacity에 용량을 차지하는 가치가 있는 물건을 최대한 담는게 목표다. 백준의 14728문제와 12865문제가 대표적이다. 두개 다 같은 코드로 작동이 가능했다.

 처음 구현을 할 때 2차원 배열을 써야하나 계속 고민을 했었는데 다른 고수들의 코드를 보니깐 1차원 배열로도 충분히 해결이 가능했었다.

• 1차원 배열을 선언 (배열의 크기는 '최대 용량의 크기 +1')
  • 여기서 배열의 인덱스의 뜻이 인덱스만큼 용량을 소모했다가 되고, 그 인덱스에 해당하는 값이 용량을 소모한 뒤 가능한 최대값이 된다.
• 이후 (차지하는 용량, 가치)를 하나씩 입력받는다
  • '(전체용량-차지하는 용량) ~ 전체 용량'만큼 for문을 돌아 비교를 하게 된다.
  • for문을 도는데 배열[전체용량-차지하는 용량]에 값이 있다면 값+가치를 한 후 인덱스에 넣는다
• 이후 반복

전체용량-차지하는용량

 1차원 배열로 문제를 푼다 했을때 제일 이해가 되지 않는 코드가 있었다\

 

    arr[i] = max(arr[i], arr[i-k]+s);

 

 for문에서 i가 최대 용량~해당 물건의 용량까지 돌고 있는데 뒤에 arr[i-k]+s는 무엇일까. 한참을 고민했었다. 고민의 정답은 예시를 넣으니 간단하게 풀렸다.

 

 위에 링크가 있는 백준의 14728 문제를 예시로 들어보자. 최대 용량은 310, 처음에 용량 50, 가치 40인 과목을 공부하게 되고 배열의 50~310은 전부 값이 40이 된다. 이후 100, 70의 입력값이 배열을 100~310을 돌게 된다.
 여기서 중요한 부분이 100~149이다. 인덱스는 이만큼 용량을 소모했다라는 뜻이다. 때문에 100~149는 값이 70이 저장이 된다. arr[i-k]를 하면 100~149는 0~49가 되니 첫번째 입력값인 50과는 관계가 없어 70만 들어가게 된 것이다.

 

 

말을 적당히 못하는게 아니라 워낙 못해서 이해가 어려울 수도 있지만 아래 코드와 함께라면 더 이해가 잘 될 것 같다.

코드

#include <iostream>
using namespace std;
int arr[10001];
int n,t,k,s;
int main(){
    scanf("%d %d", &n, &t);
    while(n--){
        scanf("%d %d", &k, &s);
        for(int i = t; i >= k; i--)
            arr[i] = max(arr[i], arr[i-k]+s);
    }
    printf("%d\n", arr[t]);
}

백준의 14728 문제 정답 코드다. 12865번도 위 배열 값만 바꿔주면 바로 적용 가능하다. 이 코드에서 제일 중요한 부분은 당연히 for문인데

• arr[i-k]+s : 남은 용량으로 값을 채운 전적이 있는가?

를 알아보는 과정이다! 라고 생각하면 이해가 편했다. 이정도면 0/1 냅색 문제는 케이크처럼 쉽게 해결할 수 있을 것 같다.
단, 들어갈 수 있는 물건이 중복되거나 다른 조건들이 있다면 또 고민해봐야 할 문제다