Python/DP BOJ-12865 평범한 가방

Posted on | In

[Python/DP] BOJ-12865 평범한 가방

배낭에 넣을 수 있는 물건의 가치합의 최댓값을 구하라

이차원 배열로 N 번째 물건까지 살펴보기 ✔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

N, K = map(int,input().split()) # N 물품의 수 / K 버틸수 있는 무게
bag_info = [[0]*(K+1) for _ in range(N+1)]
things=[]
things.append([0,0])
for _ in range(N) :
    tmp = list(map(int,input().split()))
    things.append(tmp) 

for i in range(1,N+1) :
    for j in range(1,K+1) :
        w = things[i][0]
        v = things[i][1]
        # print(w,v)
        if j < w : 
            # 남은 무게보다 물건무게가 더 큰경우 담지 않음
            bag_info[i][j] = bag_info[i-1][j]
        else :
            # 남은 무게에서 물건무게를 빼고 물건을 담는다 vs 물건을 담지 않음.
            bag_info[i][j] = max(bag_info[i-1][j], bag_info[i-1][j-w]+v)

print(bag_info[N][K])

Reference

문제 : https://www.acmicpc.net/problem/12865

풀이참고 : https://hongcoding.tistory.com/50