[알고리즘/인프런] 무게 구하기

문제

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

 

 

풀이

a를 태울지 말지를 결정하는 부분집합 문제이다.
이전 문제와 유사하지만 최대값을 구할 때 초기값은 안전하게 가능한 최소값인 Number.MIN_SAFE_INTEGER으로 초기화하도록 유의해야겠다.

 

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

  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;
}