[알고리즘] 탐욕법 - 배낭 문제 코드 (Greedy Approach - KnapSack Code)

문제)

Description

교재와 강의자료를 참고하여 분할가능한 배낭 문제를 해결하는 탐욕 알고리즘의 구현을 완성하시오.

입력은 아이템의 무게와 이익이 주어지고,

탐욕 알고리즘은 단위 무게당 이익이 가장 높은 순서대로 배낭에 담는 전략을 취한다.

입력으로 주어지는 값은 단위 무게당 이익으로 정렬되어 있지 않음에 주의하라.

단, 단위 무게당 이익이 같은 아이템은 없다고 가정해도 된다.

Input

첫째 줄에 아이템의 개수 n이 주어진다.

둘째 줄에 n개의 아이템의 무게가 주어진다.

셋째 줄에 n개의 아이템별 이익이 주어진다.

넷째 줄에 도둑의 배낭 무게 W의 개수 T가 주어진다.

다섯째 줄부터 T개의 배낭 무게 W가 주어진다.

Output

입력으로 주어진 각 W에 대해서

첫 줄에 탐욕법으로 배낭에 담을 수 있는 최대이익을 출력한다.

둘째 줄부터 배낭에 담은 아이템의 순서대로 무게와 이익의 쌍을 한 줄에 하나씩 출력한다.

다음 줄에는 다음에 주어지는 W에 대해서 위의 출력을 반복한다.

Sample Input 1

3
5 10 20
50 60 140
1
30

Sample Output 1

220
5 50
20 140
5 30

Sample Input 2

4
2 5 10 5
40 30 50 10
4
8
16
20
25

Sample Output 2

75
2 40
5 30
1 5
115
2 40
5 30
9 45
126
2 40
5 30
10 50
3 6
130
2 40
5 30
10 50
5 10

 

코드)

def func(W, items):
    temp = []       # 가방에 넣은 무게와 이익을 저장하는 리스트
    for item in items:      # 하나씩 가져옴
        if W - item[0] >= 0:
            # 만약 통쨰로 넣어도 문제가 없다면 W에서 item[1]을 뺌
            W -= item[0]
            temp.append([item[0], item[1]])     # 리스트에 넣음
        elif W > 0:
            # 통째로 넣기에는 무리가 있을 때
            temp.append([0, 0])     # 일단 0,0을 넣음
            for _ in range(item[0]):
                # 1의 무게와 무게당 이익을 추가함
                if W > 0:
                    # 아직 무게가 남아있다면 1을 뺴고 temp에 추가함
                    W -= 1
                    temp[-1][0] += 1
                    temp[-1][1] += item[2]
                elif W <= 0:
                    # 만약 무게가 꽉 찼다면 그대로 반환함
                    return temp
        else:
            # 만약 W <= 0일 때
            return temp
    # 무게를 다 못 채울 때
    return temp

if __name__ == "__main__":
    n = int(input())        # 아이템의 개수
    weight = list(map(int, input().split()))      # 아이템의 무게를 입력 받음
    profit = list(map(int, input().split()))       # 아이템의 이익을 입력 받음

    item = [(x, y, y // x) for x, y in zip(weight, profit)]      # 무게, 이익, 무게당 이익
    item.sort(key = lambda x : x[2], reverse=True)      # 무게당 이익을 기준으로 정렬함

    T = int(input())        # 도둑의 배낭 개수

    items = item
    for _ in range(T):
        W = int(input())        # 도둑의 배낭 무게
        temp = func(W, items)
        print(sum(map(lambda x : x[1], temp)))
        for t in temp:
            print(*t, sep=' ')