DFS, 부분집합

✅ 바둑이들을 트럭에 태울 때 트럭에 태울 수 있는 가장 무거운 무게를 구하세요

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

✔️ input & output

첫 줄에 c: 트럭에 최대 태울 수 있는 무게, n: 바둑이의 수가 주어집니다.

259 5
81
58
42
33
61

//output: 242

✔️ 트럭에 탈지/말지 ➡️ 부분집합 문제

앞선 부분집합 문제와 비슷 트럭에 탈지 말지 = 부분집합에 포함될지 안 될지

class Main {
    static int c;
    static int n;

    static int[] intArr;
    static int answer;


    public void DFS(int L, int sum) {
        if(sum>c) return;
        if(L==n){
            answer= Math.max(sum, answer);
        }
        else{
            DFS(L+1, sum+intArr[L]);
            DFS(L+1, sum);
        }



    }
    public static void main (String[]args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        c= sc.nextInt();
        n= sc.nextInt();
        intArr= new int[n];
        for(int i=0; i<intArr.length; i++){
            intArr[i]= sc.nextInt();
        }
        T.DFS(0, 0);
        System.out.println(answer);
    }
}

⭐️ 트럭에 태울 수 있는 무게 중, 가장 최대를 구하는 방법은? Math.max(sum, answer) 를 사용한다.