[Python Algorithm] 평범한 배낭 BOJ #12865

문제

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

12865번: 평범한 배낭

 

내 문제 풀이

n, k = map(int, input().split())
memory = [[0]*(k+1) for _ in range(n+1)] # [n+1][k+1] 크기의 0으로 채워진 배열

for i in range(1, n+1):
    w, v = map(int, input().split()) # 현재 입력된 물건의 무게, 가치
    for j in range(1, k+1):
        if w <= j: memory[i][j] = max(memory[i-1][j], memory[i-1][j-w]+v)
        else: memory[i][j] = memory[i-1][j]

print(memory[n][k])

👉 dp - 냅색 알고리즘 문제로, 무게별, 물건별 배낭이 담을 수 있는 최대 가치를 누적하는게 포인트!

• 1. 0으로 채워진 n행 k열의 memory 리스트를 생성해주었다.
  1-1) 문제에서 주어진 입력과 같이 n은 물건의 개수, k는 최대 무게를 의미하는 만큼
  memory의 행은 순서대로 입력되는 물건들을 뜻하고, 열은 1~k 무게를 뜻함!
  1-2) 무게를 1부터 k까지 모두 생성해서 보는 이유는, 담을 수 있는 최대 무게에 따른 최대 가치를
  순서대로 연산하며 결국 마지막에는 [n][k]에 누적된 값으로 최대 가치를 구하기 위함이다.
  1-3) 따라서, 아래와 같이 생각하면 된다.
  행 == 현재 물건
  열 == 배낭에 담을 수 있는 최대 무게
  [행][열] == 현재 행까지의 물건들 중, 현재 열의 무게가 최대일 경우 가능한 최대 가치
  따라서, [n][k] = n개의 물건이 있고, 배낭의 최대 무게가 k일 경우, 가능한 최대 가치!
• 2. memory 리스트의 첫 번째 요소부터 차례대로 도는 2중 for문을 생성했다.
  2-1) j가 현재 w보다 작을 경우, 현재 물건은 배낭에 넣을 수 없으므로
  이전 물건의 j열에 해당하는 [i-1][j]의 값을 그대로 [i][j]에 저장한다.
  2-2) j가 현재 w보다 같거나 클 경우, 현재 물건을 배낭에 넣을 수 있으므로
  현재 물건을 배낭에 넣는게 이득인지, 넣지 않는게 이득인지 따져봐야 한다.
  2-3) [i-1][j]와 [i-1][j-w]+v 중에서 더 큰 수가 어떤건지 보면 된다.
  여기서 잠깐,,! [i-1][j-w]+v 라는 식이 어떻게 나왔냐면,,
  현재 물건을 배낭에 넣는다면, 배낭에 남는 무게는 j-w만큼!!
  따라서 이전 행의 j-w에 해당하는 최대 가치에, 현재 물건의 가치를 더해준 값이
  바로 현재 물건을 배낭에 넣었을 때의 가치가 된다.!
  따라서 위의 두 값을 비교하여 더 큰 값을 [i][j]에 저장해주면 된다.
• 위의 1, 2번 과정을 수행하면 memory[n][k]에 누적된 최대 가치가 저장되므로,
  해당 값을 출력해주면 끝!

 

=> 위의 풀이 과정을 그림으로 나타내봤다.

memory 리스트에 모든 값이 저장된 모습을 그렸고,

대표로 볼 만한 [4][7] 자리의 요소값이 들어간 과정을 자세히 작성했다.

 

💡 피드백

• 배낭 문제를 처음 풀어봐서 풀이를 이해하는데에 굉장히 오래걸렸는데,,! 이해하니 굉장히 코드도 짧고,, 단순한? 알고리즘이었다.
• 이런 유형의 문제를 많이 풀어봐야할 것 같다.