Dog Riding

08 Aug, 2021

Problem

Cheol-su wants to go to the market with his dog. But his truck cannot carry more than C kilograms. Cheol-su wants to burn his dog the most without going over C. Given N dogs and the weight W of each dog, write a program to find the heaviest weight that Cheolsu can carry in a truck.

input

The first line is given the natural numbers C(1<=C<=100,000,000) and N(1<=N<=30)
Starting from the second row, the weights of N Go players are given

output

Print the heaviest weight on the first line.

Solution

function solution(c, arr) {
	let answer = Number.MIN_SAFE_INTEGER;

	arr.sort((a, b) => b - a);

	function DFS(L, sum) {
		let dog = arr[L];
		if (sum + dog >= c || L + 1 >= arr.length) {
			return (answer = Math.max(answer, sum));
		}

		DFS(L + 1, sum + dog);
		DFS(L + 1, sum);
	}

	DFS(0, 0);

	return answer;
}

function solution(c, arr) {
	let answer = Number.MIN_SAFE_INTEGER,
		n = arr.length;

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

	DFS(0, 0);

	return answer;
}