[알고리즘 - Python] Branch and Bound - 0-1 KnapSack Problem (분기한정법 - 0-1 배낭 문제)

문제)

Description

교재와 강의자료를 참고하여 0-1 배낭문제를 분기한정법으로 해결하는 Algorithm 6.2 의 구현을 완성하시오.

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

출력은 Best FS로 노드를 방문할 때 해당 노드의 상태를 아래와 같이 출력해야 한다.

level weight profit bound

Input

첫 줄에 아이템의 개수 n과 배낭 무게 W가 주어진다.

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

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

Output

첫 줄부터 Best FS로 방문하는 모든 노드의 상태를 출력한다.

각 상태를 출력하는 순서는 다음과 같다.

level weight profit bound

상태의 출력이 모두 끝나고 다음 줄에 최대 이익 maxprofit을 출력한다.

Sample Input 1

4 16
2 5 10 5
40 30 50 10

Sample Output 1

0 0 0 115
1 2 40 115
1 0 0 82
2 7 70 115
2 2 40 98
3 17 120 0
3 7 70 80
3 12 90 98
3 2 40 50
4 17 100 0
4 12 90 90
90

Sample Input 2

4 16
5 2 10 5
30 40 50 10 

Sample Output 2

0 0 0 115
1 2 40 115
1 0 0 82
2 7 70 115
2 2 40 98
3 17 120 0
3 7 70 80
3 12 90 98
3 2 40 50
4 17 100 0
4 12 90 90
90

코드)

from collections import deque
import heapq


class Node:
    # 노드를 만듬
    def __init__(self, level: int, weight: int, profit: int) -> None:
        self.level = level
        self.weight = weight
        self.profit = profit
        self.bound = self.setbound()

    def setbound(self) -> float:
        if self.weight >= W:
            return 0
        else:
            result = self.profit
            j = self.level + 1
            totweight = self.weight

            while j <= n and totweight + item[j][0] <= W:
                totweight += item[j][0]
                result += item[j][1]
                j += 1

            k = j
            if k <= n:
                result += (W - totweight) * item[k][1] // item[k][0]

            return result


# def bound(u: Node) -> float:
#     if u.weight >= W:
#         return 0
#     else:
#         result = u.profit
#         j = u.level + 1
#         totweight = u.weight
#
#         while j <= n and totweight + item[j][0] <= W:
#             totweight += item[j][0]
#             result += item[j][1]
#             j += 1
#
#         k = j
#         if k <= n:
#             result += (W - totweight) * item[k][1] / item[k][0]
#
#         return result


def func() -> None:
    PQ = []     # max heap임
    maxprofit = 0       # 현재까지의 최대 이익
    v = Node(0, 0, 0)
    print(v.level, v.weight, v.profit, v.bound)
    heapq.heappush(PQ, (-v.bound, v))
    # print(v.bound)
    while not len(PQ) == 0:
        v = heapq.heappop(PQ)[1]
        if v.bound > maxprofit:
            u = Node(v.level + 1, v.weight + item[v.level + 1][0], v.profit + item[v.level + 1][1])

            print(u.level, u.weight, u.profit, u.bound)

            if u.weight <= W and u.profit > maxprofit:
                maxprofit = u.profit

            if u.bound > maxprofit:
                heapq.heappush(PQ, (-u.bound, u))

            u = Node(v.level + 1, v.weight, v.profit)

            print(u.level, u.weight, u.profit, u.bound)

            if u.bound > maxprofit:
                heapq.heappush(PQ, (-u.bound, u))

    print(maxprofit)


if __name__ == "__main__":
    n, W = map(int, input().split())        # 아이템 개수, 배낭 무게
    w = list(map(int, input().split()))     # 아이템 무게 w
    p = list(map(int, input().split()))     # 아이템 이익 p
    item = [(i, j) for i, j in zip(w, p)]
    item.sort(key= lambda x: x[1] / x[0], reverse=True)       # 하나로 묶어서 내림차순으로 정렬
    item = [(0, 0)] + item

    func()

 

2번째 코드)

import heapq

class Node:
    def __init__(self, level : int, weight : int, profit : int) -> None:
        self.level = level
        self.weight = weight
        self.profit = profit
        self.bound = self.setbound()

    def setbound(self) -> float:
        # bound를 계산하는 함수, Back Tracking과 동일함
        # Back Tracking의 bound 계산 함수에 자세하게 적었으므로 참고할 것

        if self.weight >= W:
            return 0
        else:
            j = self.level + 1
            bound = self.profit
            totweight = self.weight

            while j <= n and totweight + w[j] <= W:
                totweight += w[j]
                bound += p[j]
                j += 1
            
            k = j
            if k <= n:
                bound += (W - totweight) * (p[k] // w[k])

            return bound



def knapsack6():
    PQ = list()
    maxprofit = 0       # 현재까지 찾은 최대 이득
    v = Node(0, 0, 0)       # 출발 노드를 만듬

    print(v.level, v.weight, v.profit, v.bound)

    heapq.heappush(PQ, (-v.bound, v))       # PQ에는 내림차순으로 넣어야하므로 -v.bound를 넣음
    
    while PQ:
        v = heapq.heappop(PQ)[1]        # 노드만 빼내옴
        if v.bound > maxprofit:     # 이 노드가 지금까지 찾은 최대 이득보다 크다면 탐색함
            u = Node(v.level + 1, v.weight + w[v.level + 1], v.profit + p[v.level + 1])     # 우선 다음 아이템을 넣어봄

            print(u.level, u.weight, u.profit, u.bound)

            if u.weight <= W and u.profit > maxprofit:
                # 만약 다음 아이템을 넣었을 때 위의 조건에 부합한다면 maxprofit을 바꿈
                maxprofit = u.profit

            if u.bound > maxprofit:
                # 다음 아이템을 넣었을 때 bound 값이 maxprofit보다 크면 유망하므로 자식 마디까지 탐색함
                heapq.heappush(PQ, (-u.bound, u))
            
            u = Node(v.level + 1, v.weight, v.profit)       # 이번에는 다음 아이템을 넣지 않은 상황

            # 이때 maxprofit을 갱신하지 않은 이유는 아래의 이유와 같음
            # 다음 아이템을 넣지 않았으므로 maxprofit은 현재 상황과 똑같기 때문에 갱신하지 않아도 됨

            print(u.level, u.weight, u.profit, u.bound)

            if u.bound > maxprofit:
                # 다음 아이템을 넣었을 때 bound 값이 maxprofit 보다 크면 유망하므로 자식 마디까지 탐색함
                heapq.heappush(PQ, (-u.bound, u))

    print(maxprofit)


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

# 무게당 이익으로 정렬 (내림차순)
item = [(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)

knapsack6()