[알고리즘 - Python] 동적계획법 - 0-1 배낭 문제 코드 (Dynamic Programming - KnapSack Code)

문제)

Description

교재의 내용과 강의자료를 참고하여 0-1 배낭문제를 해결하는 알고리즘의 구현을 완성하시오.

강의자료에서 knapsack2() 또는 knapsack3()를 참조할 것.

단, 입력값은 단위 무게당 이익의 순서로 정렬되어 있지 않음에 유의하시오.

또한,알고리즘 실행 결과의 출력은 알고리즘의 실행과정에서결과 테이블 P에 저장한

무게(i) 또는 이익(j)이 0이 아닌모든 항목 P[i][j]를 (i, j)의 오름차순으로 모두 출력한다는 것에 주의하시오.

Input

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

두 번째 줄에 n개의 무게 w[i]가 주어진다.

세 번째 줄에 n개의 이익 p[i]가 주어진다.

네 번째 줄에 배낭 무게의 개수 T가 주어진다.

이후로 T개의 줄에 한 줄에 하나씩 배낭 무게 W가 주어진다.

Output

주어진 배낭 무게 W 각각에 대해 다음과 같이 출력한다.

첫 줄에 최대 이익 maxprofit을 출력한다.

이후로 알고리즘의 실행과정에서 결과 테이블 P에 저장한

무게(i) 또는 이익(j)이 0이 아닌모든 항목 P[i][j]를 (i, j)의 오름차순으로 모두 출력한다

Sample Input 1

3
5 10 20
50 60 140
1
30

Sample Output 1

200
1 10 50
1 20 50
1 30 50
2 20 140
2 30 190
3 30 200

Sample Input 2

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

Sample Output 2

70
1 3 40
1 8 40
2 3 40
2 8 70
3 3 40
3 8 70
4 8 70
90
1 1 0
1 6 40
1 11 40
1 16 40
2 1 0
2 6 40
2 11 70
2 16 70
3 11 70
3 16 90
4 16 90
120
1 5 40
1 10 40
1 15 40
1 20 40
2 5 40
2 10 70
2 15 70
2 20 70
3 15 90
3 20 120
4 20 120
130
1 5 40
1 10 40
1 15 40
1 20 40
1 25 40
2 10 70
2 15 70
2 20 70
2 25 70
3 20 120
3 25 120
4 25 130

코드)

def func(n : int, W : int) -> int:
    if n == 0 or W <= 0:
        return 0

    lvalue = item.get((n - 1, W), func(n - 1, W))
    rvalue = item.get((n - 1, W - w[n]), func(n - 1, W - w[n]))
    item[(n, W)] = lvalue if w[n] > W else max(lvalue, p[n] + rvalue)

    return item[(n, W)]


if __name__ == "__main__":
    n = int(input())        # 아이템 개수
    w = list(map(int, input().split()))     # 무게
    p = list(map(int, input().split()))     # 이익
    item = list((i, j) for i, j in zip(w, p))       # 무게, 이익, 단위 무게당 이익
    item = [(0, 0, 0)] + list(sorted(item, key = lambda x : x[1] // x[0], reverse= True))        # 정렬
    w, p = zip(*item)
    T = int(input())        # 배낭 무게의 개수
    for _ in range(T):
        item = dict()
        W = int(input())        # 배낭 무게를 입력 받음
        value = func(len(w) - 1, W)
        item = list(sorted(item.items(), key = lambda x : (x[0], x[1])))
        print(value)
        for i in item:
            print(*i[0], sep=' ', end=' ')
            print(i[1])

 

2번째 코드)

def knapsack3(n: int, W: int) -> int:
    # 최대 이익을 찾는 함수
    # 이때 W는 배낭의 최대 무게가 아니라, 현재 배낭에 넣을 수 있는 최대 무게라고 봐야함

    if n == 0 or W <= 0:
        return 0

    lvalue = item.get((n - 1, W), knapsack3(n - 1, W))      # n - 1번째 아이템을 넣지 않았을 때, 값이 없다면 재귀 호출
    rvalue = item.get((n - 1, W - w[n]), knapsack3(n - 1, W - w[n]))        # n - 1번째 아이템을 넣었을 때, 값이 없다면 재귀 호출

    item[(n, W)] = lvalue if w[n] > W else max(lvalue, p[n] + rvalue)
    # 만약 n번째 아이템의 무게가 W보다 크다면, n번째 아이템을 넣지 않고,
    # 만약 아니라면 n번째 아이템을 넣거나, 넣지 않는 경우 중 큰 값을 넣음

    return item[(n, W)]


n = int(input())        # 아이템의 개수
w = list(map(int, input().split()))     # 무게
p = list(map(int, input().split()))     # 이익
T = int(input())    # 배낭 무게의 개수

item = list((i, j) for i, j in zip(w, p))       # 무게, 이익
item = [(0, 0)] + list(sorted(item, key = lambda x : x[1] // x[0], reverse= True))        # 단위 무게당 이익으로 순으로 정렬 (내림차순)
w, p = zip(*item)
# 사실 정렬은 필요 없지만, 정답을 위해선 맞춰야 함

for _ in range(T):
    W = int(input())        # 배낭 무게

    item = {}       # Hash Table
    value = knapsack3(n, W)

    print(value)

    item = list(sorted(item.items(), key = lambda x : (x[0][0], x[0][1])))      # n, W 순으로 오름차순 정렬함 (출력을 위해)
    for nW, value in item:
        print(*nW, value, sep=' ')