BOJ(평범한배낭) 12865

작성일 | In

12865 평범한 배낭

  • N개의 물건이 있고 물건은 무게 W[i]와 가치 V[i]를 갖는다.
  • 배낭에 무게 k까지만 넣을 수 있다.
  • 배낭에 넣을 수 있는 물건 가치의 최댓값을 구하는 문제
  • 각각의 물건을 배낭에 넣는 경우와 넣지 않는 경우가 있다.
  • 그러면 2^N가지의 경우가 있다.

  • 1<= N <= 100이기 때문에. 시간초과가 날 것

  • 최대 무게 K까지만 넣을 수 있다고 했다.
  • 물건이 N개 일 때, M과 N-M개로 나눴다고 하자.
  • M개 일 대, 무게가 10인데 하나는 가치가 5이고 하나가 가치가 7이라고 하면
  • 가치가 작은 건 절대로 정답이 될 수 없다.
  • 각각의 무게에 따라서 그 때 최대, 얼마의 가치를 가지는 지를 기록해서 문제를 해결해야 한다.

점화식

  • D[i][j] = i번째 물건까지 고려했고, 배낭에 넣은 물건 무게의 합이 j일 때, 가치의 최댓값
  • i번째 물건을 가방에 넣은 경우과, i번째 물건을 가방에 넣지 않은 경우 ,이렇게 나눌 수 있다.
  • i번째 물건을 가방에 넣지 않았다면, 배낭에 추가되는 게 없다. 그냥 D[i-1][j]라고 할 수 있다.
  • 가방에 넣은 경우 -> D[i-1]j-w[i]]+v[i] 이 둘 중의 최댓값이 답이 된다.
n, k = map(int, input().split())
temp = [list(map(int, input().split())) for _ in range(n)]
w, v = zip(*temp) # list형 컨테이너 타입을 unpacking할 때, *연산자가 사용된다.
w = [0] + list(w)
v = [0] + list(v)
d = [[0] * (k+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, k+1):
        d[i][j] = d[i-1][j]
        if j-w[i] >= 0:
            d[i][j] = max(d[i][j], d[i-1][j-w[i]]+v[i])
print(d[n][k])
  • 1차원 다이나믹으로도 해결할 수 있다.
  • 어차피 i-1과 i가 있으면, 이 결과를 다 복사를 내놓은 다음에 비교한다고 보면 된다.
  • 모든 i를 지워버리면 된다.
  • 대신 뒤에서부터 배열을 채우면 된다.
n,k = map(int,input().split())
temp = [list(map(int,input().split())) for _ in range(n)]
w,v = zip(*temp)
w = [0] + list(w)
v = [0] + list(v)
d = [0]*(k+1)
for i in range(1, n+1):
    for j in range(k, 0, -1):
        if j-w[i] >= 0:
            d[j] = max(d[j],d[j-w[i]]+v[i])
print(d[k])

참고자료 codeplus

0%