49)바둑이 승차(DFS)

목표

N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하기

 

조건

그의 트럭은 C킬로그램 넘게 태울 수가 없다.

 

철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.

 

제한사항

첫 번째 줄에 자연수 C(1<=C<=100,000,000)와 N(1<=N<=30)이 주어집니다.

 

둘째 줄부터 N마리 바둑이의 무게가 주어진다.

 

첫 번째 줄에 가장 무거운 무게를 출력한다.

 

문제풀이

def go(L, sum, tsum):
  global result

  if sum+(total-tsum)<result:
    return
  
  if sum>C:
    return

  if L==N:
    if sum>result:
      result=sum
  else:
    go(L+1, sum+a[L], tsum+a[L])
    go(L+1, sum, tsum+a[L])

C, N=map(int, input().split())
a=[0]*N
result=-2147000000
for i in range(N):
  a[i]=int(input())
total=sum(a)
go(0, 0, 0)

print(result)