close_btn
조회 수 889 추천 수 0 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

+ - Up Down Comment Print Files
?

단축키

Prev이전 문서

Next다음 문서

+ - Up Down Comment Print Files
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

List of Articles
번호 제목 글쓴이 날짜 조회 수
공지 우수 코드 게시판 이용 관련 공지사항 DataMarket 2014.05.21 43164
187 투빅스 11기&12기 9주차 CNN심화(1) - 12기 김주호 file 김주호 2019.09.25 1225
186 투빅스 11기&12기 9주차 CNN심화(2) - 12기 김태한 file 12기김태한 2019.09.25 878
185 투빅스 11기&12기 8주차 CNN심화(3) - 12기 배유나 file 배유나 2019.09.24 981
184 투빅스 11기&12기 8주차 CNN심화(4) - 12기 배유나 file 배유나 2019.09.24 977
183 투빅스 11기&12기 8주차 CNN - 12기 박재민 jaemin0095 2019.09.23 913
182 투빅스 11기&12기 8주차 NLP기초 - 12기 박진혁 file 박진혁 2019.09.21 947
181 투빅스 11기&12기 8주차 NLP - 12기 김주호 file 김주호 2019.09.20 857
» 투빅스 11기&12기 7주차 알고리즘(1) - 12기 김탁영 file 2019.09.19 889
179 투빅스 11기&12기 7주차 알고리즘(2) - 김효은 file 김효은 2019.09.17 836
178 투빅스 11기&12기 7주차 프레임워크(PyTorch) - 12기 신윤종 file yj 2019.09.16 889
177 투빅스 11기&12기 6주차 크롤링 - 이유진 yooj_lee 2019.09.04 874
176 투빅스 11기&12기 6주차 크롤링 - 12기 신윤종 file yj 2019.08.31 811
175 투빅스 11기&12기 6주차 크롤링 - 12기 김주호 file 김주호 2019.08.31 861
174 투빅스 11기&12기 5주차 알고리즘 - 12기 김탁영 2019.08.29 856
173 투빅스 11기&12기 5주차 SVM - 12기 이홍정 올타임넘버원메시 2019.08.27 896
172 투빅스 11기&12기 5주차 PCA - 12기 김태한 file 12기김태한 2019.08.27 927
171 투빅스 11기&12기 4주차 Ensemble - 12기 배유나 배유나 2019.08.26 892
170 투빅스 11기&12기 5주차 Class - 12기 이세윤 세윤 2019.08.26 825
169 투빅스 11기&12기 3주차 Naive bayes - 12기 김태한 12기김태한 2019.08.19 849
168 투빅스 11기&12기 4주차 Clustering - 12기 신윤종 file yj 2019.08.17 867
Board Pagination ‹ Prev 1 2 3 4 5 6 7 8 9 ... 10 Next ›
/ 10

나눔글꼴 설치 안내


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

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

설치 취소

Designed by sketchbooks.co.kr / sketchbook5 board skin

Sketchbook5, 스케치북5

Sketchbook5, 스케치북5

Sketchbook5, 스케치북5

Sketchbook5, 스케치북5