37. 예산 문제

부서별로 필요한 물품 하나씩을 신청받았습니다.

정해진 예산을 초과하는 경우 '모든 부서'의 물품을 구매해 줄 수는 없습니다. 

최대한 '많은 부서'의 물품을 구매하려고 합니다.

 

물품은 조각나지 않으며, 물품의 일부만 구매할 수 없습니다.

그래서 물품을 구매해 줄 때는 각 부서가 신청한 금액이 정확히 사용됩니다. 

예를 들어 10원짜리 물품을 신청한 부서에는 정확히 10원짜리 물품이 지원되어야 하며, 10원보다 적은 금액의 물품을 대신 구매해 줄 수는 없습니다.

재귀로 풀어보았습니다. (삽질의 시작)

def allocate_base():
    sum = 0  # 요청의 합
    index = len(request)
    count = 0  # 예산에 반영된 부서의 수
    return allocate(index, count, sum)


def allocate(index, count, sum):
    print(index, count, sum)
    if sum > budget:
        return count - 1
    elif index == 0:
        return count
    else:
        return max(allocate(index-1, count+1, sum+request[index-1]),
                   allocate(index-1, count, sum))


request = [1, 2, 3, 4, 5]  # 각 부서별 요청
budget = 7  # 총 예산
print(allocate_base())  # 4

생각의 흐름을 따라 코딩을 한 거라 좀 난잡한 느낌이 들더군요. ㅎㅎ

그래서 다시 보니 count 변수를 안 쓰고 코딩할 수 있다는 것을 알았습니다.

def allocate(index, sum):
    print(index, sum)
    if sum > budget:
        return -1
    elif index == 0:
        return 0
    else:
        return max(1 + allocate(index-1, sum+request[index-1]),
                   allocate(index-1, sum))


request = [1, 2, 2, 4, 5]  # 각 부서별 요청
budget = 5  # 총 예산
sum = 0  # 요청의 합
index = len(request)
print(allocate(index, sum))

count 변수가 없으니 깔끔해졌습니다. 

그런데 이걸 어떻게 배열을 이용한 DP(동적 계획법)로 바꿔볼까 고민하다가,
탐욕법으로 풀린다는 걸 알아버렸습니다. ㅠ,.ㅠ

나눌 수 없는 물건이라는 단어에 혹해서 탐욕법으론 안 되겠거니 한 겁니다.

def allocate(request, budget):
    request.sort()
    length = 0
    for i in range(len(request)):
        budget -= request[i]
        if budget >= 0:
            i += 1
            length += 1
        else:
            break
    return length


print(allocate([1,2,3,4,5], 10))

 

지워버리긴 아까워서, 동적 계획법으로 작성한 것을 같이 올립니다. 

뒷정리도 안한 코드 입니다. 답은 제대로 나오는 것 같네요..

동적 계획법은 배열을 어떻게 짜느냐가 풀이의 핵심인 것 같습니다. 

배낭 문제보다 배열이 더 복잡해졌네요. 

def show(array):
    for i, v in enumerate(array):
        print('b', i, v)


def allocate(request, budget):
    array = [[[0, budget] for _ in range(len(request)+1)] for _ in range(budget+1)]
    # array[b][r][0] = 예산이 b일 때, r번째 부서일 때, 지급 가능한 총 신청 부서수
    # array[b][r][1] = 예산이 b일 때, r번째 부서일 때, 남은 예산
    for b in range(1, budget + 1):
        for r in range(1, len(request) + 1):
            if request[r-1] > b:  # 남은 예산보다 요청이 큰 경우
                array[b][r] = array[b][r-1]  # 남은 예산은 그대로, 요청 무시
            else:  # 남은 예산보다 요청이 작거나 같은 경우
                if array[b-request[r-1]][r-1][0] + 1 > array[b][r-1][0]:
                    # 요청을 반영했을 때 부서수가, 하지 않았을 때 보다 클 때만, 요청을 반영한다.
                    array[b][r] = [array[b-request[r-1]][r-1][0] + 1,
                               array[b-request[r-1]][r-1][1]-request[r-1]]
                    # 지급 가능한 부서 수는 [이전 지급 가능 부서 수] 보다 [1] 증가
                    # 예산은 [이전 예산] 보다 [신청] 만큼 감소
                else:
                    array[b][r] = array[b][r-1]

    show(array)
    return array[budget][len(request)][0]


print(allocate([4, 3, 3, 1, 1], 4))  # 각 부서별 요청, 총 예산
print(allocate([1, 1, 3, 3, 4], 4))  # 각 부서별 요청, 총 예산

b 0 [[0, 4], [0, 4], [0, 4], [0, 4], [0, 4], [0, 4]]
b 1 [[0, 4], [0, 4], [0, 4], [0, 4], [1, 3], [1, 3]]
b 2 [[0, 4], [0, 4], [0, 4], [0, 4], [1, 3], [2, 2]]
b 3 [[0, 4], [0, 4], [1, 1], [1, 1], [1, 1], [2, 2]]
b 4 [[0, 4], [1, 0], [1, 0], [1, 0], [2, 0], [2, 0]]
2
b 0 [[0, 4], [0, 4], [0, 4], [0, 4], [0, 4], [0, 4]]
b 1 [[0, 4], [1, 3], [1, 3], [1, 3], [1, 3], [1, 3]]
b 2 [[0, 4], [1, 3], [2, 2], [2, 2], [2, 2], [2, 2]]
b 3 [[0, 4], [1, 3], [2, 2], [2, 2], [2, 2], [2, 2]]
b 4 [[0, 4], [1, 3], [2, 2], [2, 2], [2, 2], [2, 2]]
2