[AlgorithmSolving][DP] JUNGOL_1077: 배낭채우기1

1. 문제 내용

• 문제:

  정올 보석상에 도둑이 침입했다. 도둑은 배낭에 보석을 훔치려고 한다. 이때, 훔친 보석의 무게가 W를 넘어가면 배낭이 망가진다. 각 보석의 값어치와 무게가 주어질 때, 도둑은 총 무게가
  W를 넘지 않으면서 보석의 총 값어치가 최대가 되도록 보석을 배낭에 담으려고 한다. 이때 배낭에 담을 수 있는 최대 값어치를 구하시오.

• 입력:

  첫 줄은 보석의 가지 수 N(1≤N≤1,000)과 배낭의 용량 W(1≤W≤10,000)가 주어진다. 둘째 줄부터 N+1줄에는 각 보석의 무게 W_i(1≤W_i≤W)와 값어치 P_i가 주어진다.

  (단, 각각의 보석의 개수는 무제한으로 가정한다.)

• 출력:

  보석의 무게와 값어치가 주어질 때 총 무게가 W를 넘지 않으면서, 보석의 총 값어치가 최대가 되는 최대값을 출력한다.

  최대값은 int 범위 이내이다.

2. 문제 유형 파악

해당 문제는 DP 문제로 DP 유형 중 하나인 무한 배낭 문제입니다.

3. 문제를 풀기 위한 핵심 아이디어

1. 문제를 풀기 위해선 0/1 배낭 문제처럼 2차원 배열을 쓸 수 없고 1차원 배열을 사용해야함.
2. 배낭에 채울 수 있는 보석의 개수가 무한개이기 때문에 0/1 배낭 문제의 점화식과는 다른 점화식을 사용한다. 점화식은 다음과 같다.

\[DP[i] = \begin{cases} \max(DP[i], DP[i-W_i] + P_i) & \text{if } w \ge W_i \end{cases}\]

4. 코드

무한 배낭 문제의 코드는 0/1 배낭 문제보다는 코드가 간단합니다. 코드는 다음과 같습니다.

import sys

input = sys.stdin.readline

n, w = map(int, input().split())

DP = [0 for _ in range(w+1)]

for _ in range(n):
    weight, value = map(int, input().split())

    for j in range(1, w+1):
        if j >= weight:
            DP[j] = max(DP[j], DP[j-weight]+value)

print(DP[w])

300

5. 복기 및 최적화

5.1 코드 복기

제가 짠 코드를 보면 j가 1부터 시작합니다만 j가 weight보다 작을 때는 if문 조건이 거짓이 되어 아무런 작업도 하지 않고 반복문만 헛돌게 되는 비효율적인 부분이 있습니다.

5.2 최적화

Gemini의 도움을 받아 코드 최적화를 진행해 보았습니다.

j의 시작점을 weight부터 시작하도록 range를 수정하면 if문 자체를 없앨 수 있습니다. 분기문 if이 사라지면 연산 속도가 눈에 띄게 빨라지면 코드도 간결해집니다.

import sys

input = sys.stdin.readline

n, w = map(int, input().split())

# 1차원 DP 배열 선언
DP = [0] * (w + 1)

for _ in range(n):
    weight, value = map(int, input().split())

    # [최적화] 1부터가 아닌, 현재 보석의 무게(weight)부터 w까지 정방향 탐색!
    # 무의미한 반복을 줄이고 if 조건문을 제거하여 실행 속도 향상
    for j in range(weight, w + 1):
        DP[j] = max(DP[j], DP[j - weight] + value)

print(DP[w])

300