java) 부분 집합 문제 DFS로 해결하기

 

문제

철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다.
철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.
N마리의 바둑이와 각 바둑이의 무게 W가 주어지면,
철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.

 

입력

첫 번째 줄에 자연수 C(1<=C<=100,000,000)와 N(1<=N<=30)이 주어집니다.

둘째 줄부터 N마리 바둑이의 무게가 주어진다.

 

출력

첫 번째 줄에 가장 무거운 무게를 출력한다.

 

입력

259 5
81
58
42
33
61

출력

242

 

 

위와 같은 문제를 보면 부분 집합 문제라는 것을 알 수 있을 것이다. 즉 바둑이를 트럭에 태울 것인지, 안 태울 것인지 경우의 수를 나누어 최대 무게를 안넘기는 가장 큰 무게를 가질 수 있는 경우를 찾으면 된다. 바로 DFS를 이용하여 풀어보자,

 

그림을 보면 이해하기 쉬울 것 이다.

 

 

 

이런 트리 구조를 일일이 만들어 주어야 할까? 아니다. 아래 자바 코드를 보면서 이해하자.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int answer = Integer.MIN_VALUE, n, m;
    static int[] dogs;

    public static void dfs(int level, int sum, int[] dogs){
        
        // sum이 259를 넘으면
        if (sum > n) return;
        // 말단 노드까지 더했으면
        if (level == m){
            answer =  Math.max(answer, sum);
        }
        // dfs 계속 도는 경우
        else{
            dfs(level+1, sum + dogs[level], dogs); // 다음 값을 더한다
            dfs(level+1, sum, dogs); // 다음 값을 더하지 않는다
        }
    }

    public static void main(String[] args)throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        dogs = new int[m];

        for (int i = 0 ; i < dogs.length ; i++){
            dogs[i] = Integer.parseInt(br.readLine());
        }

        dfs(0,0, dogs);
        System.out.println(answer);
    }
}