DP / Knapsack 문제https://www.acmicpc.net/problem/7579 냅색(Knapsack) 알고리즘간단하게 말하면, 한 도둑이 훔치는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.출처: 위키피디아 냅색 알고리즘은 담을 수 있는 물건이 나눌 수 있냐 없냐에 따라 나눈다. 담을 수 있는 물건이 나누어 질 때(설탕 몇 g 등): 분할가능 배낭문제(Fractional Knapsack Problem)담을 수 있는 물건이 나누어 질 수 없을 때(담는다 or 안담는다): 0-1 배낭문제(0-1Knapsack Problem)해당 문제는 0-1 배낭문제의 경우다.  일반적인 배..

DP / Knapsack 문제https://www.acmicpc.net/problem/12865  냅색(Knapsack) 알고리즘 냅색 알고리즘은 대표적인 동적 계획법(DP) 문제 중 하나로, 주어진 가방에 담을 수 있는 무게 제한과 각 물건의 가치를 고려하여 최대한의 가치를 얻는 문제다. 이 알고리즘은 크게 두 가지 유형으로 나뉜다. 1. 분할 가능한 배낭 문제 (Fractional Knapsack): 물건을 부분적으로 쪼개어 담을 수 있는 경우에 해당한다.각 물건의 가치를 무게로 나눈 값(즉, 무게 대비 가격 비율)을 기준으로 물건을 정렬하여 높은 비율 순서대로 가방에 담는다.가방의 남은 용량보다 물건의 무게가 크다면, 물건을 잘라서 넣는다. 이렇게 하면 쉽게 최대 가치를 얻을 수 있다.2. 0-1 ..