문제
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
풀이
이미 다룬 적 있는 알고리즘이다.
0/1 Knapsack Problem - Dynamic Programming (tistory.com)
0/1 Knapsack Problem - Dynamic Programming
얼만큼의 비용과 보상이 정해진 여러개의 물체가 있다고 하자. 특정 용량까지 수용 가능한 마대에 이 물체들을 마대의 최대 수용량을 넘기지 않게 넣어주되, 담겨있는 물체들의 보상의 합이 가
forteqook.tistory.com
중요한것은 i 번째 물건을 가방에 넣는 경우, 안넣는 경우 중 값어치가 최대가 되는 것을 계속 고르면 된다는 것이다.
N,K = map(int,input().split())
W = [0]
V = [0]
for _ in range(N):
w,v = map(int,input().split())
W.append(w)
V.append(v)
dp = [[0]*(K+1) for _ in range(N+1)]
for i in range(1,N+1):
for j in range(1,K+1):
dp[i][j] = max(dp[i-1][j], dp[i-1][j-W[i]]+V[i]) if j >= W[i] else dp[i-1][j]
print(dp[N][K])'PS > 백준' 카테고리의 다른 글
| 10986번 - 나머지 합 (0) | 2022.11.04 |
|---|---|
| 11659번 - 구간 합 구하기 4 (0) | 2022.11.04 |
| 9251번 - LCS (0) | 2022.11.04 |
| 2565번 - 전깃줄 (0) | 2022.11.04 |
| 11054번 - 가장 긴 바이토닉 부분 수열 (0) | 2022.11.04 |