[알고리즘]DFS - 바둑이 승차

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

 

 

import java.util.Scanner;

public class Main { // DFS
	static int answer = Integer.MIN_VALUE, k, n; // answer : 트럭에 태울 수 있는 최대 무게
	
	public static void DFS(int level, int sum, int[] arr) {
		if (sum>k) return;
		if (level==n) {
			answer = Math.max(answer, sum);
		}
		else {
			DFS(level+1, sum+arr[level], arr); // 트럭에 태움
			DFS(level+1, sum, arr); // 안 태움
		}
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		k = scanner.nextInt(); // 트럭 최대 무게
		n = scanner.nextInt(); // 바둑이 마리 수
		int[] arr = new int[n]; // 바둑이들 무게
		for (int i=0; i<n; i++) {
			arr[i] = scanner.nextInt();
		}
		DFS(0, 0, arr); // level, sum, arr
		System.out.println(answer);
	}

}

---

259 5
81
58
42
33
61
242