[ 자바스크립트(JavaScript) ] section08 - 6 - 바둑이 승차(DFS)

📍 section08 - 6 - 바둑이 승차(DFS)

문제: 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다고 한다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게는 무엇일까요?

 

1. 부분집합을 이용한 문제다.
2. 주어진 배열에서 부분집합을 구한 후 weight보다 작은 값 중 최댓값을 갱신시키는 방법으로 푼다.
3. DFS 의 인자를 2개로 설정한 다음 weight 값을 누적시키거나 누적시키지 않는 방법을 사용한다.

 

728x90

 

let weight = 259;
let n = 5;
let arr = [81, 58, 42, 33, 61];

console.log(solution(weight, n, arr));

function solution(weight, n, arr){
  let answer = Number.MIN_SAFE_INTEGER;
  arr.sort((a,b)=>b-a);

  function DFS(L, sum){
    if (sum > weight) 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;
}