083 - 최대점수 구하기(Knapsack 알고리즘)

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩 니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)

 

 

▣ 입력설명
첫 번째 줄에 문제의 개수N(1<=N<=100)과 제한 시간 M(10<=M<=1000)이 주어집니다.
두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.

 

▣ 출력설명
첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.

 

▣ 입력예제 1

5 20
10 5
25 12
15 8
6 3
7 4

 

▣ 출력예제 1

41

 

 

 

이중 리스트와 단일 리스트를 이용한 풀이 방법입니다. 두개의 방식 차이에서 오는 소비시간도 같이 표시하였습니다.

 

import time
import copy
import sys
name = 'in5.txt'
#sys.stdin = open(name, 'rt')

if __name__ == '__main__':
    n, m = map(int, input().split())
    print(f'name:{name},    n:{n}, m:{m}')
    pt = list()
    tm = list()
    for i in range(n):
        a, b = map(int, input().split())
        pt.append(a)
        tm.append(b)

    # =============== Dynamic, Single list ===============
    print('=============== Dynamic, Single list ===============')
    start = time.time()
    dy = [0]*(m+1)
    for i in range(n):
        p, t = pt[i], tm[i]
        for j in range(m, t-1, -1):
            if dy[j] < dy[j-t]+p:
                dy[j] = dy[j-t]+p
        # print(f'dy:{dy}')
    end = time.time()
    print(f'result:{dy[-1]}, time:{(end-start)*1000:5.5} ms')
    print()

    # =============== Dynamic, Single list ===============

    # =============== Dynamic, Dual list ===============
    print('=============== Dynamic, Dual list ===============')
    start = time.time()
    dy = [[0]*(m+1) for _ in range(n+1)]

    for i in range(1, n+1):
        p, t = pt[i-1], tm[i-1]
        dy[i] = copy.deepcopy(dy[i-1])
        for j in range(t, m+1):
            if dy[i][j] < dy[i-1][j-t]+p:
                dy[i][j] = dy[i-1][j-t]+p
    end = time.time()
    print(f'result:{dy[n][m]}, time:{(end-start)*1000:5.5} ms')
    # =============== Dynamic, Dual list ===============

 

 

 

 

name:in5.txt,    n:19, m:150

=============== Dynamic, Single list ===============
result:252, time:0.73004 ms

=============== Dynamic, Dual list ===============
result:252, time:2.5189 ms