[골드 V] 12865번. 평범한 배낭

 문제 

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

12865번: 평범한 배낭

 사용 언어 

Python3

 풀이 과정 

이 문제는 "배낭 문제 알고리즘"의 기본 중의 기본 문제였다. 그래서 문제 이름도 평범한 배낭!

그런데 문제 유형은 코딩 테스트에서 몇 번 접해본 것 같았다. 이게 배낭 문제라는 알고리즘으로 취급되는지 몰랐을 뿐.

그래서 이번 기회에 확실히 공부해두려 했는데 생각보다 이해가 좀.. 어려웠다는 것?!

관련 문제 레벨이 최소 골드에서 시작하는 이유가 있었다...

 

어쨌든 개념만 보고 혼자 풀어보려다가 포기하고 상세한 블로그를 보고 이해한 뒤 맞았습니다!!

뭔가 반만 이해한 느낌이라 며칠 뒤에 다시 복습이 필요할 것 같다.

 

 제출 답안 

# N개의 물건은 W의 무게와 V의 가치를 가짐
# 최대 K개의 무게만 넣을 수 있는 가방
# 가치의 최댓값은?

from itertools import product
from sys import stdin
input = stdin.readline

N, K = map(int, input().split())
products = [tuple(map(int, input().split())) for _ in range(N)]
# dp[i][j]는 무게 i에 대해 물건 j를 담거나 담지 않는 경우 중 최댓값
dp = [[0 for _ in range(K + 1)] for _ in range(N)]
for i in range(0, N):
    for j in range(1, K + 1):
        weight = products[i][0]
        value = products[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 - 1][K])

 

 공부한 내용 

배낭 문제 알고리즘

배낭 문제 알고리즘은 배낭을 쪼갤 수 있냐(?) 없냐에 따라 두 가지로 나뉜다.

분할 가능한 배낭 문제는 그리디 알고리즘을 사용해 풀 수 있고, 이 문제와 같이 분할 불가능한 0-1 배낭문제는 동적 계획법, 혹은 백트래킹 방법을 이용해서 문제를 해결할 수 있다.

 

- 동적 계획법

def knapsack2(i, W, w, p):
    if (i <= 0 or W <= 0):
        return 0
    if (w[i] > W):
        value = knapsack2(i - 1, W, w, p)
        print(i - 1, W, value)
        return value
    else: # w[i] <= W
        left = knapsack2(i - 1, W, w, p)
        print(i - 1, W, left)
        right = knapsack2(i - 1, W - w[i], w, p)
        print(i - 1, W - w[i], right)
        return max(left, p[i] + right)

- 백트래킹

def knapsack3 (i, profit, weight):
    global maxprofit, numbest, bestset
    if (weight <= W and profit > maxprofit):
        maxprofit = profit
        numbest = i
        bestset = include[:]
    if (promising(i, profit, weight)):
        include[i + 1] = True
        knapsack3(i + 1, profit + p[i+1], weight + w[i+1])
        include[i + 1] = False
        knapsack3(i + 1, profit, weight)

def promising (i, profit, weight):
    if (weight > W):
        return False
    else:
        j = i + 1
        bound = profit
        totweight = weight
        while (j <= n and totweight + w[j] <= W):
            totweight += w[j]
            bound += p[j]
            j += 1
        k = j
        if (k <= n):
            bound += (W - totweight) * p[k] / w[k]
        return bound > maxprofit

 

출처: https://namu.wiki/w/%EB%B0%B0%EB%82%AD%20%EB%AC%B8%EC%A0%9C | https://chanhuiseok.github.io/posts/improve-6/