문제)
Description
교재와 강의자료를 참고하여 0-1 배낭문제를 해결하는 Algorithm 5.7을 완성하시오.
단, 문제의 입력은 단위무게당 이익순으로 정렬되어 있지 않음에 유의하시오.
또한, 알고리즘의 출력은 알고리즘의 실행 단계별로
상태공간트리의 각 노드에서의 상태를 출력해야 함에 주의하시오.
Input
첫번째 줄에 아이템의 개수 n과 배낭의 무게 W가 주어진다.
두번째 줄에 n개의 아이템 무게 w[i]가 주어진다.
세번째 줄에 n개의 아이템 이익 p[i]가 주어진다.
Output
첫 번째 줄부터 한 줄에 하나씩 상태공간트리를 방문하는 노드의 상태를 출력하시오.
노드 상태는 다음과 같은 순서로 출력한다.
i weight profit bound maxprofit
상태를 출력하는 순서는 Algorithm 5.7의 노드 실행 순서이다. (즉, DFS with Pruning의 노드 순회 순서임)
노드의 상태 출력이 끝나는 다음 줄에 최대이익을 출력한다.
이후로 배낭에 담은 아이템을 한 줄에 하나씩 무게와 이익 순서로 출력한다.
아이템을 출력하는 순서는 처음에 단위무게당 이익으로 정렬한 순서대로 출력함에 주의할 것.
코드)
from copy import deepcopy
def promising(i : int, profit : int, weight : int) -> tuple:
global bound, totweight
if weight >= W:
return False
else:
j = i + 1
bound = profit
totweight = 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 > maxprofit
def func(i : int, profit : int, weight : int) -> None:
global maxprofit, bestset, bound, totweight
if weight <= W and profit > maxprofit:
maxprofit = profit
bestset = deepcopy(include)
flag = promising(i, profit, weight)
print(i, weight, profit, bound, maxprofit)
if flag:
include[i + 1] = True
func(i + 1, profit + p[i + 1], weight + w[i + 1])
include[i + 1] = False
func(i + 1, profit, weight)
if __name__ == "__main__":
n, W = map(int, input().split()) # 아이템 개수
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)
maxprofit = 0
include = [0] * (len(w) + 1)
bestset = [0] * (len(w) + 1)
totweight = 0
bound = 0
func(0, 0, 0)
print(maxprofit)
for i in range(1, n + 1):
if bestset[i]:
print(w[i], p[i])
2번째 코드)
from copy import deepcopy
### 참고로 마디가 유망한것과 maxprofit을 업데이트 하는 것은 엄연히 다른 과정임
def promising(i : int, profit : int, weight : int) -> bool:
global bound, totweight
if weight >= W:
# 만약 현재까지의 무게가 W보다 크거나 같다면 자식 마디는 유망하지 않음
return False
else:
j = i + 1
bound = profit # global로 참조했지만, profit과 weight로 초기화 하기 때문에 상관은 없음
totweight = weight
while j <= n and totweight + w[j] <= W:
# i + 1에서 k - 1까지 갔을 때의 무게와 그때까지의 이익을 계산함
# 만약 j가 n보다 커진다면 다 담아도 터지지 않는다는 뜻임
totweight += w[j]
bound += p[j]
j += 1
k = j
if k <= n:
# 만약에 k가 n보다 작다면, i번째 마디의 자식 마디에 대한 이익의 상한선을 구함
bound += (W - totweight) * (p[k] // w[k])
return bound > maxprofit
def func(i : int, profit : int, weight : int) -> None:
global maxprofit, bestset
if weight <= W and profit >= maxprofit:
# 지금까지 담은 무게가 W보다 작고, 아이템의 이익이 지금까지 얻은 최대 이익보다 크거나 같다면 업데이트함
maxprofit = profit
bestset = deepcopy(include)
flag = promising(i, profit, weight) # bound를 업데이트 하기 위해 미리 실행함
print(i, weight, profit, bound, maxprofit)
if flag:
# 넣었을 때의 경우
include[i + 1] = True
func(i + 1, profit + p[i + 1], weight + w[i + 1])
# 넣지 않았을 때의 경우
include[i + 1] = False
func(i + 1, profit, weight)
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)
maxprofit = 0 # 최대 이익
include = [0] * (n + 1) # 지금까지 담은 아이템, 1이면 해당 인덱스의 아이템을 담은 것
bestset = [0] * (n + 1) # 최대 이익일 때의 set
totweight = 0 # 특정 마디일 때의 무게 합
bound = 0 # 특정 마디일 때 자식 마디로 갔을 때의 이익의 상한선
func(0 ,0, 0)
print(maxprofit) # 최대 이익을 출력
for i in range(1, n + 1):
if bestset[i] == 1:
print(w[i], p[i])