문제
철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 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>
내가 짱이다 😎 매일 조금씩 성장하기🌱
9/17
종료코드
if(sum>c) return;가 반드시 있어야함