바둑이 승차

철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다.

철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.

N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.

입력

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

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

출력

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

 

입력                                   출력

259 5                                 242    
81
58
42
33
61

 

dfs를 이용해서 죽 더하면서 더한 값이 무게 제한을 넘지 않는 최대값인 것을 구하는 문제

 

부분집합 dfs 전 문제와 비슷하다

 

import java.util.*;


public class Main{
    static int total = 0;
    static int[] arr;

    static int max = Integer.MIN_VALUE, high;

    public void dfs(int v, int sum){
        if (sum > high) return;
        if( v == arr.length){
            if (sum > max && sum <= high) max = sum;
        }
        else {
            dfs(v+1, sum + arr[v]);
            dfs(v+1, sum);
        }
    }

    public static void main(String args[]) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);

        high = in.nextInt();
        int n = in.nextInt();
        arr = new int[n];
        for (int i =0; i< n; i++) {
            arr[i] = in.nextInt();
            total += arr[i];
        }

        T.dfs(0, 0);

        System.out.print(max);
    }
}