💡문제
이 문제는 아주 평범한 배낭에 관한 문제이다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.
입력
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.
입력으로 주어지는 모든 수는 정수이다.
출력
한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.
예제입력
4 7
6 13
4 8
3 6
5 12예제출력
14📖내가 작성한 Code
import sys
'''
배낭 문제
'''
def knapsack(goal, array):
dp = [0]*(goal + 1)
for weight, value in array:
for j in range(goal, weight - 1, -1):
dp[j] = max(dp[j], dp[j - weight] + value)
return dp[-1]
def main():
inputs = map(str.split, sys.stdin.read().splitlines())
n, k = map(int, next(inputs))
obj = [list(map(int, next(inputs))) for _ in range(n)]
print(knapsack(k, obj))
if __name__ == '__main__':
main()✍️풀이과정
전형적인 배낭문제라 위와 같이 풀었다. 0/1 배낭 문제이므로
for j in range(goal, weight - 1, -1):이런식으로 뒤에서부터 해줘야한다. 그런데 매우 흥미로운 점이 있는데
마침 내가 세 달전에 이 문제를 풀었다.
import heapq
N,K = map(int,input().split())
mono = [[0,0]]
bag = [[0 for _ in range(K+1)] for _ in range(N+1)]
for _ in range(N):
heapq.heappush(mono,list(map(int,input().split()))[::-1])
for i in range(1, N+1):
for j in range(1, K+1):
w = mono[i][1]
v = mono[i][0]
if j < w:
bag[i][j] = bag[i-1][j]
else:
bag[i][j] = max(bag[i - 1][j-w]+v,bag[i-1][j])
print(bag[N][K])특이한 점이 보이는데,
- 전역으로 풀었음
- 변수명이 통일이 안되어 있음
- heapq를 이용하여 가치순으로 정리하고 0/1 문제를 해결함
- 모든 무게를 기준으로 하였다.
그래서 코드 읽기가 너무 어려웠음. 결과 또한 아래와 같다.
좋은 방향으로 더 나아가야겠다는 생각을 하게 되었다.
또 특이한 점은 다른 사람이 최적화 한 코드를 보면 알 수 있다.
import sys
def knapsack(goal, array):
dp = {0: 0}
for weight, value in array:
temp = {}
for v, w in dp.items():
if dp.get(nv := value + v, goal) > (nw := weight + w):
temp[nv] = nw
dp.update(temp)
return max(dp.keys())
def main():
inputs = map(str.split, sys.stdin.read().splitlines())
n, k = map(int, next(inputs))
obj = sorted([tuple(map(int, next(inputs))) for _ in range(n)], key=lambda x: x[0], reverse=True)
sys.stdout.write(str(knapsack(k+1, obj)))
if __name__ == '__main__':
main()
list 사용을 지양하고, dict를 사용하였다. 그리고 get, update등을 통하여 최적화 하였다. 매우 이쁜 코드. 본 받아야겠다.
🧠 코드 리뷰
- 주석의 추가 : 정렬의 목적 및 효과를 명확히 하는 주석 추가가 도움이 됩니다.
🛠️AI 개선 코드
import sys
def knapsack(max_capacity, items):
"""
0/1 배낭 문제를 동적 계획법(DP)을 통해 해결합니다.
각 상태 dp[v]는 가치 합 v를 달성하는데 필요한 최소 무게를 저장합니다.
Parameters:
max_capacity (int): knapsack의 최대 허용 무게 + 1 (즉, 실제 제한은 max_capacity - 1)
items (list of tuples): 각 튜플은 (무게, 가치)
Returns:
int: 제한 무게 내에서 달성 가능한 최대 가치
"""
# dp[value] = 최소 무게 (가치 0은 무게 0으로 시작)
dp = {0: 0}
for weight, value in items:
# 현재 아이템을 추가하여 생성될 새로운 상태들을 임시 저장
new_states = {}
for curr_value, curr_weight in dp.items():
new_value = curr_value + value
new_weight = curr_weight + weight
# 새로운 상태가 유효한 경우(총 무게가 제한 미만)만 고려
if new_weight < max_capacity:
# 기존에 동일 가치의 상태가 없거나, 더 가벼운 무게로 달성할 수 있다면 갱신
if new_value not in dp or new_weight < dp[new_value]:
new_states[new_value] = new_weight
# 임시 저장한 새로운 상태들을 dp에 반영
dp.update(new_states)
# dp에 저장된 가치 중 최대값이 문제의 정답
return max(dp.keys())
def main():
# 전체 입력을 한 번에 읽은 후, 각 줄을 분리합니다.
input_lines = sys.stdin.read().splitlines()
# 첫 줄에는 아이템의 개수 n과 knapsack의 용량 k가 주어집니다.
n, k = map(int, input_lines[0].split())
# 이후 n개의 줄에 걸쳐 (무게, 가치) 튜플을 읽어옵니다.
items = [tuple(map(int, line.split())) for line in input_lines[1:1+n]]
# 최적화를 위한 정렬: 무게가 큰 아이템부터 처리합니다.
# (꼭 필요한 것은 아니지만, 일부 경우에 불필요한 상태 업데이트를 줄일 수 있습니다.)
items.sort(key=lambda x: x[0], reverse=True)
# knapsack 함수에서는 max_capacity를 k+1로 전달하여,
# 내부에서 new_weight < max_capacity 조건을 통해 실제 용량 k를 제한합니다.
result = knapsack(k + 1, items)
sys.stdout.write(str(result))
if __name__ == '__main__':
main()
💻결과
🖱️참고 링크
