[BOJ] Q7579 앱

[BOJ] Q7579 앱

Question

Language: Python

Difficulty: Gold 3

비활성화할 앱 몇개를 선택하는데, 이때 선택된 앱들은 재기동 할때 비용이 발생하는데, 이때의 비용을 최소화 하도록 하는 문제이다. 이러한 문제는 대표적인 0/1 knapsack의 문제이다.

메모리의 비용을 무게로 볼 수 있고, 용량을 가치로 두고 문제를 풀이할 수 있다. 그리고 0/1 knapsack를 이용해 array을 채워가면서 용량이 요구하는 용량 이상이 되면 비용 값을 최신화 한다.

Solution

items,required_memories=map(int,input().split())
app_memories=[0] + list(map(int,input().split()))
app_weights=[0] + list(map(int,input().split()))

max_weight=sum(app_weights)
bag=[[0]*(max_weight+1) for _ in range(items+1)]
z
min_weight=max_weight
for item in range(1,items+1):
    for weight in range(1,max_weight+1):
        if app_weights[item] > weight:
            bag[item][weight]=bag[item-1][weight]
        else:
            bag[item][weight]=max(bag[item-1][weight],bag[item-1][weight-app_weights[item]]+app_memories[item])
        if bag[item][weight]>=required_memories:
            min_weight=min(min_weight,weight)
print(min_weight)