크래프톤 정글 6기 TIL - Day 16 | Knapsack Problem

Knapsack Problem

배낭의 최대 용량이 W일 떄, 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법.

DP로 해결할 수 밖에 없는 문제이다!

 

- i 번째 보석이 배낭의 한도보다 무거우면 안되므로, i번째 보석을 뺀 i-1개의 보석들을 가지고 구한 전단계의 최적값을 그대로 가지고 온다.

- 그렇지 않은 경우 , i번째 보석을 위해 i번째 보석 만큼의 무게를 비웠을 때, 최적 값에 i번째 보석의 가격을 더한 값 or i-1개의 보석들을 가지고 구한 전단계의 최적값 중 큰걸 선택한다.

 

 

12865. 평범한 배낭

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

import sys
input = sys.stdin.readline


# 물품의 수, 배낭의 최대 무게
N, K = map(int, input().split())

Weights = [0 for _ in range(N+1)]
Value =  [0 for _ in range(N+1)]

for i in range(1,N+1):
    W,V = map(int, input().split()) 
    
    Weights[i] = W
    Value[i] = V
  
# 가치합의 최댓값 구하기
results = [ [0 for _ in range(K+1)] for _ in range(N+1)] #2차원 배열에 경우에 따른 최대값을 저장해둔다.

for i in range(1,N+1):
    for w in range(1,K+1):
        if w - Weights[i] >= 0:
            # 그전 무게를 넣었을 때와 가치비교해서 높은 가치를 넣는다.
            results[i][w] = max(results[i-1][w],results[i-1][w-Weights[i]]+Value[i])  # 자리가 남으면 들어갈수잇는 가치가 높은 다른 물건을 넣는다.
        else:
            results[i][w] = results[i-1][w]
            
            
print(results[N][K])
    
# 문제를 잘못봐가지고 중복값이 있는줄알았다ㅠㅜㅠ 흑흑 드냥 다 배열로 해서 품