정보 선생님은 예산이 많은 부서에서 일하고 있다.
학기말이 가까워지면서 부서의 예산을 가급적 모두 집행해야 될 상황이 되었다.
정보 선생님은 예산 범위를 넘지 않는 범위 내에서 다양한 활동을 하고 싶어한다.
지금 남은 예산(B)이 40이고(단위:만원), 예산을 사용할 수 있는 활동(N)이 6개가 있다.
6개의 활동에 각각 드는 비용은 7, 13, 17, 19, 29, 31이다.
여기서 40을 채울 수 있는 활동의 개수는 상관이 없다.
40을 넘지 않는 범위에서 활동 비용을 조합해보면,
7 + 13 + 17 = 37
7 + 31 = 38
7 + 13 + 19 = 39
...
따라서 40을 초과하지 않으면서 예산을 최대로 사용할 수 있는 비용은 39이다.
정보 선생님을 도와 줄 수 있는 프로그램을 작성하시오.
첫째 줄에 남은 예산(B)가 입력된다. ( 10 <= B <= 35,000 )
둘째 줄에 예산을 사용할 수 있는 활동의 수(N)이 입력된다. (1 <= N <= 21 )
셋째 줄에 공백을 기준으로 N개의 활동비가 양의 정수로 입력된다.
40
6
7 13 17 19 29 31
남은 예산을 초과하지 않으면서 최대로 사용할 수 있는 비용액을 출력하시오.
39
주어진 입력 예시대로 진행하였고, 백트래킹 사용하여 코드를 작성하였다.
예산이 초과되지 않아야 하기때문에, 예산이 초과되기 이전까지의 예산의 합을 case에 넣었고, 해당 case 내 최대값을 구하는 방법으로 진행하였다.
처음에 작성하였을때, 재귀는 돌아가나 종료조건이 없어서 종료 조건을 따로 넣어주었다.
B = int(input())
N = int(input())
N_list = list(map(int, input().split()))
def backtracking(B, N_list, visited, path, budget, case):
if budget > B:
return
else:
#case.append(path.copy())
case.append(budget)
if len(path) == len(N_list):
return
for i in range(len(N_list)):
if not visited[i]:
visited[i] = True
path.append(N_list[i])
budget += N_list[i]
backtracking(B, N_list, visited, path, budget, case)
visited[i] = False
path.pop()
budget -= N_list[i]
case = []
backtracking(B, N_list, [False] * N, [], 0, case)
print(max(case))