#1535 안녕

이번 문제는 효율적으로 풀려면 백팩 알고리즘을 이용하셔야 합니다.

 

백팩 알고리즘은 유명한 문제로, 일반적으론 결정 트리를 이용해서 예측 값이 가장 좋은 것을 먼저 선택해서 처리합니다.  그리고 결정된 값보다 나쁜 것은 제거함으로써 그나마 빠르게 계산할 수 있습니다.

 

https://www.acmicpc.net/problem/1535

1535번: 안녕

 

문제 자체는 Silver II 문제입니다.  배낭 문제로 해석을 하자면 99만큼의 무게를 넣을 수 있는 배낭에 무게 \(h_i\)이고 가치가 \(v_i\)인 물건을 넣을 때, 총 가치의 합이 최대가 되도록 하는 문제입니다.

 

배낭 문제를 결정 트리를 이용해서 처리한다면 효율적이겠지만, 저는 그냥 백트래킹을 이용해서 모든 경우를 탐색하여 최대값을 찾았습니다.

 

제가 작성한 소스입니다.  소스는 참조용으로 봐주세요.

//------------------------------------------------------------------------
//    baekjoon #1535 - Good Morning!
//        - by Aubrey Choi
//        - created at 2019-10-29
//------------------------------------------------------------------------
#include <stdio.h>

int n, h[20], v[20];
int getMax(int c, int r, int s)
{
    if(c==n) return s;
    int t = getMax(c+1, r, s);
    if(h[c] >= r) return t;
    s = getMax(c+1, r-h[c], s+v[c]);
    return s>t?s:t;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&h[i]);
    for(int i=0;i<n;i++) scanf("%d",&v[i]);
    printf("%d\n", getMax(0, 100, 0));
}