냅색

[python] SWEA - 3282. 0/1 Knapsack

🤔문제 해결 D3 | DP( Knapsack ) 💨 냅색알고리즘 💨 각 아이템에 대해서 가방의 크기를 0부터 1씩 최대무게까지 늘려가며 계산. 💨 가방의 크기가 해당 아이템의 무게보다 작으면 아이템을 넣지 못한다. 이전까지의 무게와 가치 적용 💨 가방의 크기가 해당 아이템의 무게보다 크면 아이템을 넣을지 말지 선택한다. 💨💨 이전까지의 무게와 가치 vs (이전까지의 무게 - 현재 아이템의 무게)의 가치 + 현재 아이템의 가치 💻소스 코드 # 입력 T = int(input()) Ns = [] for tc in range(T): N, K = map(int, input().split()) items = [list(map(int, input().split())) for _ in range(N)] Ns.appen..

[python] 백준 - 12865. 평범한 배낭

🤔문제 해결 G5 | DP, 냅색 알고리즘(배낭 알고리즘) 딱 봐도 너무 복잡해 보이는 DP... 2차원 배열로 풀어야할 것 같다. 행은 각 아이템, 열은 현재 무게(?) 아이템 하나를 고른다. 가방의 버틸 수 있는 무게를 0부터 M까지 올려본다. 해당 무게별로 최대로 채울 수 있는 가장 큰 값을 채운다. 사실 그렇게 딱!!! 완전히 이해는 하지 못했다... 역시 DP는 어려움 나중에 비슷한 문제를 한번 더 풀면 이해가 가지 않을까... 💻소스 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) # 물품 수, 최대 무게 items = [tuple(map(int, input().split())) for _ in range(N)..