투빅스 11기&12기 7주차 알고리즘(1) - 12기 김탁영

by 탁 posted Sep 19, 2019
?

단축키

Prev이전 문서

Next다음 문서

ESC닫기

가 + - Up Down Comment Print
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
'''
    <DP로 풀 경우>
    Memoization을 위해 모든 짐의 개수와 모든 무게에 대한 이차원 리스트를 생성한다.
        개수와 무게가 0인 경우의 값은 모두 0이다.
    i번째 짐의 무게가 기준용량보다 크다면 <i-1번째 짐까지 사용한 최적해>가 정답이다.
    i번째 짐의 무게가 기준용량보다 크지 않다면 최적해는
        i번째 짐을 포함하지 않는 경우, <i-1번째 짐까지 사용한 최적해>
        i번째 짐을 포함하는 경우, <기준용량에서 i번째 짐 무게를 뺀 상황에서의 i-1번째 최적해 + i번째 짐 무게>
    * 예: 짐 3개, 최대무게 15, 짐 [1,12,16]
    개수\무게 |  0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
    --------------------------------------------------------------------------    
        0   |  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
        1   |  0   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
        2   |  0   1   1   1   1   1   1   1   1   1   1   1   12  13  13  13  
        3   |  0   1   1   1   1   1   1   1   1   1   1   1   12  13  13  13
    >> 시간복잡도는 O(NX)이다. (N: 짐의 개수, X: 최대 무게)

    ==============================================================================

    <모든 경우의 수를 구할 경우>
    1. 1개를 고르는 경우
        - 성공: (1), (12)
        - 실패: (16)
    2. 2개를 고르는 경우
        - 성공: (1, 12)
        - 실패: (1, 16), (16, 12)
        
    3. 3개를 고르는 경우
        - 성공: 없음
        - 실패: (1, 16, 12)

    >> 시간복잡도는 O(2^N)이다.
'''
 
# Dynamic Programming (0-1 knapsack algorithm을 참고하였습니다.)
def wk7_1():
    N, X = input().split(' ')
    N, X = int(N), int(X) # N:짐 개수, X:최대용량
    bags = [int(bag) for bag in input().split()]
 
    memo = [[0 for _ in range(X+2)] for _ in range(N+2)] # 이전의 최적해를 기억해야 하므로 행과 열을 하나씩 더한다. (Out of range 방지)
 
    # 0번째 행과 열은 짐 또는 한계무게가 존재하지 않음을 의미하기 때문에 0으로 할당된다.
    for b in range(1, N+1): 
        for k in range(1, X+1):
            if bags[b-1] > k: # 짐의 무게가 한계무게를 초과했을 경우, 이전의 최적해로 할당
                memo[b][k] = memo[b-1][k]
            else: # <이전 최적해> vs. <이번 짐을 추가한다고 했을 때, 이번 짐을 제외한 여유무게에 대한 최적해 + 이번 짐의 무게>
                memo[b][k] =  max(memo[b-1][k], bags[b-1] + memo[b-1][k-bags[b-1]])
 
    print(memo[N][X])
    
if __name__ == '__main__':
    wk7_1()
 
cs
Trackback http://www.datamarket.kr/xe/board_BoGi29/62999/342/trackback

Articles

2 3 4 5 6 7 8 9 10 11

나눔글꼴 설치 안내


이 PC에는 나눔글꼴이 설치되어 있지 않습니다.

이 사이트를 나눔글꼴로 보기 위해서는
나눔글꼴을 설치해야 합니다.

✔ 설치 취소

Designed by sketchbooks.co.kr / sketchbook5 board skin

Sketchbook5, 스케치북5

Sketchbook5, 스케치북5

Sketchbook5, 스케치북5

Sketchbook5, 스케치북5