문제

인프런 문제 난이도: ⭐⭐

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

예시 1

Input: C = 259, N =  5, W = [81, 58, 42, 33, 61] 
Output: 242

풀이 1: DFS

def baduk(weight_list):
    w_list = weight_list
    
    def DFS(i, sum):
        global max_sum
        if sum > C:
            return
        if i == N:
            if max_sum <= sum:
                max_sum = sum
            return

        else:
            DFS(i+1, sum+w_list[i])
            DFS(i+1, sum)
    DFS(0, 0)
    return max_sum
N = 5
max_sum = 0
switch = 1
C = 259
weight_list = [81, 58, 42, 33, 61]
print(baduk(weight_list))