[백준] 19942번 : 다이어트

https://www.acmicpc.net/problem/19942

19942번: 다이어트

해당문제는 모든 경우의 수를 확인하여 최저 값을 찾아내는 완전탐색 + 백트래킹 문제이다.

재귀함수를 통하여 현재 아이템을 포함하는 경우와 포함하지 않은 경우로 나누어 경우의 수를 만들어 비용의 최소값을 초기화 한 후

다음 조합을 계산할때는 이전에 계산했던 최소비용보다 높을 경우 백트래킹(탐색중단) 한다.

from copy import deepcopy
N = int(input())
mp, mf, ms, mv = map(int, input().split()) # 단,지,탄,비
table = [[0, 0, 0, 0]]
for _ in range(N):
    table.append(list(map(int, input().split()))) # 단,지,탄,비, 가격


minvalue = 2001 # 최소값 두는 문제가 있음.
minqueue = []
def diet(nut, cost, depth, queue): # depth 네이밍룰 idx
    global minvalue
    global minqueue
    if cost > minvalue: # 백트래킹 조건
        return 2001
    
    if nut[0] >= mp and nut[1] >= mf and nut[2] >= ms and nut[3] >= mv: # 최소값 초기화
        if minvalue > cost:
            minqueue = queue
            minvalue = cost
        return minvalue
    
    if depth == N+1:
        return 2001

    newnut = deepcopy(nut)
    newqueue = deepcopy(queue)
    newcost = cost + table[depth][4]
    newqueue.append(depth)
    
    for i in range(4):
        newnut[i] += table[depth][i]
    
    # 해당 아이템을 현재 반영한경우와 반영하지 않은 경우 모두 탐색
    result = min(diet(newnut, newcost, depth+1, newqueue), diet(nut, cost, depth+1, queue))
    
    return result

nut = [0, 0, 0, 0]
queue = []
diet(nut, 0, 1, queue)

if minvalue == 2001:
    print(-1)
else:
    print(minvalue)
    print(*minqueue)