[Algorithm 문제 유형 분석] knapsack(베낭 문제) 쉽게 구현하기

포인트는

윗줄에서 무게뺀거 + 새로운 아이템 가치랑, 그냥 윗줄이랑 비교해서 더 무거운걸 채우는거다

 

아직 현 아이템을 채울 정도의 weight이 되지 않았다면 그냥 윗줄꺼를 채워주면 된다.

for i in range(1, N + 1):
    for j in range(1, K + 1):
        weight = stuff[i][0]
        value = stuff[i][1]

        if j < weight:
            knapsack[i][j] = knapsack[i - 1][j]
        else:
            knapsack[i][j] = max(value + knapsack[i - 1][j - weight], knapsack[i - 1][j])

 

 

[문제 유형]

평범한 베낭 - 아이템이 한종류

카우버거 알바생