12865-백준-평범한 배낭

1. 문제 출처

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

12865번: 평범한 배낭

 

2. 풀이

• 해당 문제는 흔히 Knapsack 알고리즘 문제이다
• 가방의 담을 수 있는 무게가 정해져 있을 때, 최대한 가치를 가지도록 배낭을 싸는 문제이다..
• 이를 다음과 같이 정의할 수있다.
  • 1.현재 배낭의 한계량 보다 큰 무게의 물건은 넣지 않는다.
  • 2.현재 배낭의 한계량 보다 작은 무게라면 더 좋은 가치의 물건을 넣는다.
    • 2-1 무게와 물건이 0이라면 결과도 0이다
    • 2-2 현재 무게 < 선택한 물건의 무게 이면 배낭에 물건을 추가하지 않는다.
    • 2-3 위의 경우가 아니라면 해당 물건 만큼의 무게를 빼고 해당 물건의 가치를 더한 것과 그대로 가지고 가는 것을 비교한다

# 한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.



n ,k = map(int, input().split(" "))
# 0,0은 아무것도 못넣었을 때 이다..
stuffList = [(0,0)]

# dp[n][k] --> 는 n번째 물건을 보았을 때 무게가 k인 배낭의 최대 가치이다.
dp = [[0]*(k+1) for _ in range(n+1)]

## overweight_count 무게가 최대 무게를 넘는 물건은 미리 빼주었다.
overweight_count = 1

for idx in range(n):
    W ,V = map(int, input().split(" "))
    if W <= k :  
        stuffList.append((W,V))
    else:
        overweight_count+=1
        
n = len(stuffList) - overweight_count



# 다이나믹 프로그래밍 botton-up 방식을 사용하였다.
# 2-1 을 위해 1부터 시작
if n == 0 :
    print(0)
else:
    for i in range(1 , n+1):
        for j in range(1,k+1):
            weight = stuffList[i][0]
            value = stuffList[i][1] 
            if j < weight:
                
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight]+value)
            
    print(dp[n][k])

 

무게가 넘는 것을 미리 빼주면 229220kb -> 227036kb 로 메모리 사용량이 줄었고 시간은 그대로 였다.