Computer Science/알고리즘

[알고리즘 - Python] 되추적 - 0-1 배낭문제 코드 (BackTracking - 0-1 KnapSack Code)

바보1 2022. 5. 15. 22:33

문제)

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의 노드 순회 순서임)

노드의 상태 출력이 끝나는 다음 줄에 최대이익을 출력한다.

이후로 배낭에 담은 아이템을 한 줄에 하나씩 무게와 이익 순서로 출력한다.

아이템을 출력하는 순서는 처음에 단위무게당 이익으로 정렬한 순서대로 출력함에 주의할 것.

Sample Input 1

4 16
2 5 10 5
40 30 50 10

Sample Output 1

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

Sample Input 2

4 16
5 2 5 10
30 40 10 50

Sample Output 2

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

코드)

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])