[python 파이썬] 백준 12865번 평범한 배낭
2021. 2. 9. 00:11ㆍAlgorithm/BOJ
반응형
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
N,K = map(int, input().split())
weight = [0]
gold =[0]
for _ in range(N):
w, g= map(int, input().split())
weight.append(w)
gold.append(g)
dp=[[0 for i in range(K+1)] for k in range(N+1)]
for w in range(1, N+1):
for i in range(1, K+1):
if i>= weight[w]:
dp[w][i]=max(dp[w-1][i], dp[w-1][i-weight[w]]+gold[w])
else:
dp[w][i]=dp[w-1][i]
print(dp[N][K])반응형
'Algorithm > BOJ' 카테고리의 다른 글
| [python 파이썬] 백준 11660번 구간합구하기5 (0) | 2021.02.15 |
|---|---|
| [python 파이썬] 백준 11659번 구간합구하기 4 (0) | 2021.02.15 |
| [python 파이썬] 백준 1535번 안녕 (0) | 2021.02.09 |
| [python 파이썬] 백준 1739번 타일링 (0) | 2021.02.05 |
| [python 파이썬] 백준 2565번 파이썬 (0) | 2021.02.05 |