[Python, 파이썬] SWEA 3282. 0/1 Knapsack

물건 몇개를 선택해 가방에 넣을 수 있는 최대 가치를 구하는 문제.

 

1번부터 N번까지의 번호가 부여된 N(1≤N≤100)개의 물건과 최대 K(1≤K≤1000) 부피만큼을 넣을 수 있는 가방이 있다.

물건은 각각 부피 Vi와 가치 Ci를 가지고 있을 때, 가방에 넣을 수 있는 물건의 최대 가치의 합을 구하는 문제.

 

T = int(input()) # 테스트케이스의 개수 T

for test_case in range(1, T+1):

    N, K = map(int, input().split()) # 물건의 개수 N, 가방의 부피 K
    V = [0 for i in range(N)] # 부피 정보
    C = [0 for i in range(N)] # 가치 정보

    pq = [(0, 0)] # 조합을 저장할 리스트
    max_value = 0
    visited = {}  # 이미 본 (부피, 가치)를 저장할 딕셔너리

    for i in range(N):
        Vi, Ci = map(int, input().split())
        V[i] = Vi # 부피 정보 저장
        C[i] = Ci # 가치 정보 저장

    # 탐색 시작
    for i in range(N):

        for v, c in pq.copy():

            if v + V[i] > K:  # 최대 부피보다 클 시
                continue

            new_v = v + V[i]  # 새로운 부피
            new_c = c + C[i]  # 새로운 가치

            # 같은 부피가 있을 경우 더 큰 가치만 유지
            if new_v not in visited or visited[new_v] < new_c:

                if(new_v in visited):
                    pq.remove((new_v, visited[new_v])) # 이전 값 큐에서 삭제
                
                visited[new_v] = new_c  # 더 큰 가치를 저장
                max_value = max(new_c, max_value)  # 최대 가치 업데이트
                pq.append((new_v, new_c))  # 리스트에 값 삽입


    print("#%d %d" % (test_case, max_value))

 

 

 

 

[문제풀이]

---

 

이 문제는 딱 보고 DFS+백트래킹 문제란 생각이 들었다.

그런데 N이 100개면 2의 100승이고 그럼 시간복잡도가 너무 커져서 주어진 시간 내에 풀 수 없다.

 

그래서 DP를 사용해 푸는 SWEA 3752번이랑 딕셔너리를 응용해서 풀었다.

 

 

우선 각 조합의 (부피, 가치)를 저장하는 리스트를 하나 만든다.

그리고 여기에 swea 3752문제처럼 물건 하나당 선택할 경우, 선택하지 않을 경우의 조합을 만들었다.

 

그런데 이 조합을 모두 저장하는 방식으로 하면 Runtime Error, 즉 메모리 부족 문제가 생긴다.

그래서 최대 부피를 넘는 거는 저장하지 않게 했다.

if v + V[i] > K:  # 최대 부피보다 클 시
    continue

 

또, 딕셔너리에 각 부피당 최대값을 저장하여 새로 같은 부피가 들어올 경우 검사한다.

그래서 그 값이 최대일 경우 딕셔너리를 그 값으로 업데이트하고 이전에 큐에 저장되있었던 같은 부피의 값을 지운다.

if(new_v in visited):
    pq.remove((new_v, visited[new_v])) # 이전 값 큐에서 삭제
                
visited[new_v] = new_c  # 더 큰 가치를 저장

 

 

이렇게 하면 큐에는 각 부피당 최대 가치값이 저장되며, 이 중 가장 큰 가치를 지니는 값이 배낭에 넣을 수 있는 최대 가치다.

 

처음엔 간단하게 생각했는데 생각보다 어려웠다.

근데 이거, 풀고 나니까 음 완전한 DP로 푸는 문제더라.....

다음에 DP로 다시 한번 풀어봐야겠다.