BOJ 12865 평범한 배낭

생성일

2024/08/09 05:32

태그

다이나믹 프로그래밍

배낭 문제

URL

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

이번 문제는 배낭 문제(Knapsack Problem)로 DP의 예제로 잘 알려진 문제입니다. https://www.acmicpc.net/problem/12865

문제 설명

•

NNN: 물건의 개수

•

KKK: 배낭에 넣을 수 있는 무게 제한

•

물건들은 적절하게 배낭에 담아서 나올 수 있는 가치합의 최댓값을 구하는 문제

예제 입력/출력

•

입력1

Plain Text
복사

•

출력1

Plain Text
복사

제약 조건

•

1≤N≤1001 ≤ N ≤ 1001≤N≤100

•

1≤K≤100,0001 ≤ K ≤ 100,0001≤K≤100,000

•

물건에 대한 제약 조건

◦

1≤물건의무게≤100,0001 ≤ 물건의 무게 ≤ 100,0001≤물건의무게≤100,000

◦

0≤물건의가치≤1,0000 ≤ 물건의 가치 ≤ 1,0000≤물건의가치≤1,000

문제 풀이

풀이1 브루트 포스 - O(2N)O(2^N)O(2N)

풀이2 그리디

풀이3 DP - O(N⋅K)O(N \cdot K)O(N⋅K)

풀이 코드

•

Bottom-Up 방식의 구현

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 for _ in range(K + 1)] for _ in range(N + 1)]

for n in range(1, N + 1):
    for k in range(1, K + 1): # dp[n][k]
        dp[n][k] = dp[n - 1][k]
        if k - W[n] >= 0:
            dp[n][k] = max(dp[n][k], dp[n - 1][k - W[n]] + V[n])

print(dp[N][K])
Python
복사

Top-Down 방식의 구현