제로칼로리
2023. 3. 8. 21:07
코드
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
class 바둑이승차DFS{
static int answer=Integer.MIN_VALUE, c, n;
static int[] arr;
static int sum;
void DFS2(int L) {
if(sum>c) return;
if(n==L) {
System.out.println(answer+" "+sum);
answer = Integer.max(answer, sum);
return ;
} else {
sum+=arr[L];//가산 했을때
DFS2(L+1);
sum-=arr[L];//가산 안했을때
DFS2(L+1);
}
}
public void DFS(int L, int sum, int[] arr){
if(sum>c) return;
if(L==n){
answer=Math.max(answer, sum);
}
else{
DFS(L+1, sum+arr[L], arr);
DFS(L+1, sum, arr);
}
}
public static void main(String[] args){
바둑이승차DFS T = new 바둑이승차DFS();
arr= ThreadLocalRandom.current()
.ints(10, 100)
.distinct()
.limit(5)
.toArray();
//제한 무게
c = Arrays.stream(arr).sum()/2;
n=arr.length; //받은 요소 수
System.out.println(Arrays.toString(arr));
T.DFS2(0);
System.out.println("제한무게 "+c);
System.out.println("최대무게 "+answer);
}
}
결과
[34, 84, 50, 63, 49]
-2147483648 118
118 133
133 84
133 97
133 83
133 34
133 134
134 133
134 84
134 113
134 99
134 50
134 112
134 63
134 49
134 0
제한무게 140
최대무게 134
모든 경우의 수를 따라 제한무게에 최대한 같은 수 찾기