[Python]알고리즘/백준
[다이나믹 프로그래밍] ★★ 12865번 - 평범한 배낭(22.05.15 복습완료)
[백준] 12865번 - 평범한 배낭 (한줄평) 냅색 문제인지 모르고 풀었던... 생각보다 더 어려웠던 문제로 복습이 꼭 필요하다!!! 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. N개의 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 구하는 문제다. 이 문제는 전형적인 냅색 문제다. 1. 분할가능 배낭 문제(Fractional Knapsack Problem) 담을 수 있는 물건이 나누어질 때(설탕 몇 g) - 물건의 가격을 무게로 나누어 무게 대비 가격이 비싼 순서로 물건을 정렬해서 넣으면 쉽게 해결이 가능! - 배낭이 감당할 ..
