목록백준 평범한배낭 (1)

바위 뚫는중

[Python] 냅색 알고리즘 (Knapsack Problem), 백준 12865. 평범한 배낭

🎒 Knapsack Problem 한 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제 담을 수 있는 물건이 나누어 질 때 → 분할가능 배낭문제 → 그리디 알고리즘으로 해결할 수 있음 담을 수 있는 물건이 나누어질 수 없을 때 → 배낭 문제 🥇 평범한 배낭 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을..
Algorithms/백준 2024. 2. 29. 16:49
이전 Prev 1 Next 다음