[Softeer / Level2] 금고털이

https://www.softeer.ai/practice/info.do?idx=1&eid=395 

Softeer

---

 

 

분할 가능한 knapsack 문제이다.

분할이 불가능한 경우면 dp로 풀어야 하는데, 그렇지 않다면 그리디로 해결한다.

 

밸류값을 기준으로 소팅하고 제한된 W에 알맞게 가져가도록 코드를 구성했다.

 

<내 코드>

import sys

total_weight = 0
total_value = 0
W, N = map(int, input().split())
S = []
for i in range(N):
    a, b = map(int, input().split())
    S.append((a, b))

S.sort(key=lambda x: -x[1])

for weight, value in S:
    if total_weight + weight <= W:
        total_value += weight * value
        total_weight += weight
    elif total_weight + weight > W:
        total_value += abs(W - total_weight) * value
        break

print(total_value)