0/1 냅색 문제 풀기

husk321·2021년 1월 14일
0

20-21알고리즘 공부

목록 보기
1/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 냅색 문제는 케이크처럼 쉽게 해결할 수 있을 것 같다.
단, 들어갈 수 있는 물건이 중복되거나 다른 조건들이 있다면 또 고민해봐야 할 문제다

profile
게임 개발자 지망

0개의 댓글