문제)
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을 출력한다.
코드)
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()
'Computer Science > 알고리즘' 카테고리의 다른 글
[알고리즘 - Python] Dynamic Programming - TSP (동적계획법 - 외판원 순환 문제) (0) | 2022.05.29 |
---|---|
[알고리즘 - Python] Branch and Bound - TSP (분기한정법 - 외판원 순환 문제) (0) | 2022.05.29 |
[알고리즘 - 이론] The Selection Problem and the Adversary Argument (선택 문제와 적대적 논쟁) (1) | 2022.05.27 |
[알고리즘 - 이론] Computational Complexity (계산 복잡도) (2) | 2022.05.27 |
[알고리즘 - 이론] Branch-and-Bound Strategy (분기한정법) (0) | 2022.05.27 |