# 12865 평범한 배낭(Python 파이썬)

 

N, K = map(int, input().split())  # 물품의 수 N, 최대 무게 K 입력 받기
items = [(0, 0)]  # 물건의 무게와 가치를 저장할 리스트, 0번 인덱스는 사용하지 않기 위해 초기값 설정
for _ in range(N):
    W, V = map(int, input().split())  # 각 물건의 무게 W와 가치 V 입력 받기
    items.append((W, V))

# dp[i][w]: 처음 i개의 물건을 고려했을 때, 무게 w까지의 배낭에 담을 수 있는 최대 가치
dp = [[0 for _ in range(K+1)] for _ in range(N+1)]

for i in range(1, N+1):
    for w in range(1, K+1):
        if items[i][0] <= w:  # i번째 물건을 배낭에 넣을 수 있는 경우
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-items[i][0]] + items[i][1])
        else:  # i번째 물건을 배낭에 넣을 수 없는 경우
            dp[i][w] = dp[i-1][w]
    # 현재 dp 테이블 상태 출력
    print(f"After considering item {i} (Weight: {items[i][0]}, Value: {items[i][1]}):")
    for row in dp:
        print(row)
    print("-" * 50)

print(f"Maximum value in the knapsack of weight {K}: {dp[N][K]}")

 

C:\Users\redcu\PycharmProjects\baekjoon\.venv\Scripts\python.exe C:\Users\redcu\PycharmProjects\baekjoon\knapsack.py 
4 7
6 13
4 8
3 6
5 12
After considering item 1 (Weight: 6, Value: 13):
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 13, 13]
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]
--------------------------------------------------
After considering item 2 (Weight: 4, Value: 8):
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 13, 13]
[0, 0, 0, 0, 8, 8, 13, 13]
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]
--------------------------------------------------
After considering item 3 (Weight: 3, Value: 6):
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 13, 13]
[0, 0, 0, 0, 8, 8, 13, 13]
[0, 0, 0, 6, 8, 8, 13, 14]
[0, 0, 0, 0, 0, 0, 0, 0]
--------------------------------------------------
After considering item 4 (Weight: 5, Value: 12):
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 13, 13]
[0, 0, 0, 0, 8, 8, 13, 13]
[0, 0, 0, 6, 8, 8, 13, 14]
[0, 0, 0, 6, 8, 12, 13, 14]
--------------------------------------------------
Maximum value in the knapsack of weight 7: 14

종료 코드 0(으)로 완료된 프로세스

N, K = map(int, input().split())
items = [(0, 0)]  # 더미 원소
for _ in range(N):
    W, V = map(int, input().split())
    items.append((W, V))

dp = [0 for _ in range(K+1)]

for i in range(1, N+1):
    w, v = items[i]
    # 역순 DP 업데이트
    for j in range(K, w-1, -1):
        dp[j] = max(dp[j], dp[j-w] + v)

print(dp[K])​

4 7
6 13
4 8
3 6
5 12


초기 DP 테이블: [0, 0, 0, 0, 0, 0, 0, 0]

물건 1: 무게 6, 가치 13
무게 7에서 최대 가치 업데이트: 0 -> 13
무게 6에서 최대 가치 업데이트: 0 -> 13
업데이트 후 DP 테이블: [0, 0, 0, 0, 0, 0, 13, 13]

물건 2: 무게 4, 가치 8
무게 7에서 기존 최대 가치 유지: 13
무게 6에서 기존 최대 가치 유지: 13
무게 5에서 최대 가치 업데이트: 0 -> 8
무게 4에서 최대 가치 업데이트: 0 -> 8
업데이트 후 DP 테이블: [0, 0, 0, 0, 8, 8, 13, 13]

물건 3: 무게 3, 가치 6
무게 7에서 최대 가치 업데이트: 13 -> 14
무게 6에서 기존 최대 가치 유지: 13
무게 5에서 기존 최대 가치 유지: 8
무게 4에서 기존 최대 가치 유지: 8
무게 3에서 최대 가치 업데이트: 0 -> 6
업데이트 후 DP 테이블: [0, 0, 0, 6, 8, 8, 13, 14]

물건 4: 무게 5, 가치 12
무게 7에서 기존 최대 가치 유지: 14
무게 6에서 기존 최대 가치 유지: 13
무게 5에서 최대 가치 업데이트: 8 -> 12
업데이트 후 DP 테이블: [0, 0, 0, 6, 8, 12, 13, 14]

최종 최대 가치: 14

종료 코드 0(으)로 완료된 프로세스

https://hongcoding.tistory.com/50

[백준] 12865 평범한 배낭(Python 파이썬)

https://youtu.be/XZjKsOVryls