8-6) 바둑이 승차(DFS)

7482 단어 DFSDFS

문제

철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태 울수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.
N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.
[입력설명]
첫 번째 줄에 자연수 C(1<=C<=100,000,000)와 N(1<=N<=30)이 주어집니다. 둘째 줄부터 N마리 바둑이의 무게가 주어진다.
[출력설명]
첫 번째 줄에 가장 무거운 무게를 출력한다.

입력예제 1

259 5
81
58
42
33
61

출력예제 1

242

문제 풀이

코드

  • 태울 수 있는 경우의 수, 즉 {81, 58, 42, 33, 61}의 부분집합의 수는 2^5-1=31개이다.(공집합 제외)
  • 코드 전체의 원리는 다음과 같다.
<html>
    <head>
        <meta charset="UTF-8">
        <title>출력결과</title>
    </head>
    <body>
        <script>
            function solution(c, arr){
                let answer=Number.MIN_SAFE_INTEGER; //max값 구해야하니까 가장 작은 숫자로 초기화
                let n=arr.length;
                function DFS(L, sum){
                    if(sum>c) return; //제한 (이코드 없으면 전체 합 나옴)
                    if(L===n){
                        //console.log(sum);
                        answer=Math.max(answer, sum);
                    }
                    else{
                        DFS(L+1, sum+arr[L]); //포함하는 경우
                        DFS(L+1, sum); //포함하지 않는 경우
                    }
                }
                DFS(0, 0);
                return answer;
            }

            let arr=[81, 58, 42, 33, 61];
            console.log(solution(259, arr));
        </script>
    </body>
</html>
데스크톱 플로팅 창 (악성 광고) 의 구현 설명
자바 TCP 소켓 프로그래밍(채팅프로그램)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage