DP: knapsack problem (1)

 

n개의 물건이 각각 다른 가치, 무게를 가지고 있다고 하자.

나의 배낭에는 무게 w만큼의 물건을 담을 수 있다.

 

제한된 용량을 가진 배낭(Knapsack)에 최대한의 가치를 넣어보자.

 

---

 

물건을 하나씩 넣으면서, 넣는 경우와 안 넣는 경우를 비교하며 최대값을 선택하면 된다.

 

• dp[i][w]: i번째 물건까지 고려했을 때, 배낭용량이 w인 경우 얻을 수 있는 최대 가치

물건을 넣지 않는 경우, 넣는 경우 비교하여 최대값 선택

 

이 경우 시간 복잡도는 O(n*w)이다.

 

---

 

역시 문제를 풀어봐야 제 맛

knapsack 문제집: https://www.acmicpc.net/workbook/view/19494 OR https://www.acmicpc.net/problemset?sort=ac_desc&algo=148

 

✘ 백준 1535 안녕

 

classic knapsack problem

import sys
input = sys.stdin.readline

n = int(input())
losing = [0]+list(map(int, input().split()))
happiness = [0]+list(map(int, input().split()))

dp = [[0 for _ in range(101)] for _ in range(n+1)]

for i in range(1, n+1):
    for w in range(1,101):
        if losing[i] <= w:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-losing[i]]+happiness[i])
        else:
            dp[i][w] = dp[i-1][w]

print(dp[n][99])

 

• 메모리 최적화 (1차원 DP 배열 사용): 2차원 DP로 시뮬레이션을 돌려서 전처럼 구현했으나 1차원으로도 아주 가능.
  • 2차원 DP) dp[i][w] : i번째 사람까지 고려했을 때, 남은 체력 w인 경우 얻을 수 있는 행복
  • 1차원 DP) dp[i] : i번째 사람까지 고려했을 때, 얻을 수 있는 행복
    => ⭐️ 체력을 역순으로 순회하며, 현재 상태 업데이트 하기 전에 이전 상태 유지 가능! 
• 배열 크기 설정: dp[i][101]로 왜 설정함? dp[i][100]만 쓰는데. 이런 부분 항상 꼼꼼하게 봤으면...조켄네...

 

import sys
input = sys.stdin.readline

n = int(input())
losing = [0] + list(map(int, input().split()))
happiness = [0] + list(map(int, input().split()))

dp = [0] * 100 

for i in range(1, n+1):
    for remaining_hp in range(99, losing[i] - 1, -1):
        dp[remaining_hp] = max(dp[remaining_hp], dp[remaining_hp - losing[i]] + happiness[i])

print(dp[99])

 

---

✘ 백준 12865 평범한 배낭

 

위에서 배운 1차원 dp 바로 써봤습니다

import sys
input = sys.stdin.readline

n,m = map(int, input().split()) # 물건 종류 / 가방 최대 무게
stuff = [[0,0]]

for _ in range(n):
	w, v = map(int, input().split()) # 물건 무게 / 물건 가치
	stuff.append([w, v])

dp = [0 for _ in range(m+1)]

for i in range(1, n+1):
	cur_w = stuff[i][0]
	cur_v = stuff[i][1]

	for j in range(m, cur_w-1, -1):
		dp[j] = max(dp[j], dp[j-1], dp[j-cur_w]+cur_v)

print(dp[-1])

 

• 변수명: index로 cur_w, cur_v 따로 또 정리해서 쓸거면 그냥 stuff 자체를 for문 돌리자
• dp[j-1]은 왜..? 불필요함

 

import sys
input = sys.stdin.readline

n,m = map(int, input().split()) # 물건 종류 / 가방 최대 무게
stuff = [list(map(int, input().split())) for _ in range(n)]

dp = [0 for _ in range(m+1)]

for weight, value in stuff:
    for j in range(m, weight - 1, -1):
        dp[j] = max(dp[j], dp[j - weight] + value)

print(dp[-1])

 

 

---

✘ 백준 4781 사탕 가게

1차원 DP로 풀었는데 시간초과가 났다...

시간복잡도는 O(n * m)

 

돈의 양이 소수점 두 자리까지 주어진다하여 100배를 하였는데, 이것이 문제일까요...

 

import sys
input = sys.stdin.readline


while True:
    # n: 사탕 종류 수, m: 상근이 돈
    n, m = map(float, input().split())
    n = int(n)
    m = int(m*100)

    if n == 0 and m == 0.00:
        break
    
    candies = []

    for _ in range(n):
        # 칼로리 c와 가격 p
        c, p = map(float, input().split()) 
        candies.append([int(c), int(p*100)])
    
    dp = [0 for _ in range(m+1)]

    for calori, price in candies:
        for i in range(price, m+1):
            dp[i] = max(dp[i-1], dp[i-price]+calori)
    
    print(dp[-1])

 

 

아직 해결 못함...

 

---

 

✘ 백준 9084  동전

 

dp에 방법 수를 넣어주면서 업데이트

 

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    n = int(input())
    coins = list(map(int, input().split()))
    m = int(input())

    dp = [0 for _ in range(m+1)]
    dp[0] = 1

    for coin in coins:
        for i in range(coin, m+1):
            dp[i] += dp[i-coin]

    print(dp[-1])

 

---

 

✘ 백준 1106 호텔

 

원하는 최소 고객을 맞추기 위해 필요한 최소 비용 찾는 문제

import sys
input = sys.stdin.readline

c, n = map(int, input().split()) # c: 원하는 최소 고객 수, n: 도시 수
cities = list(list(map(int, input().split())) for _ in range(n)) # 비용, 고객

dp = [sys.maxsize for _ in range(c+101)]
dp[0] = 0

for cost, customer in cities:
    for i in range(customer, c+101):
        dp[i] = min(dp[i], dp[i-customer]+cost)
        
print(min(dp[c:]))

 

---

 

대충 어떻게 쓰는 건지 구조만 알겠는 느낌

다음에 문제를 더 풀어봐야할 것 같습니다...