배낭 문제

문제 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 메모리 M 이상을 확보하기 위해서 필요한 비용의 최소값을 구해야 하는 문제입니다. 즉, 메모리 M 이상을 확보하기 위해 앱을 비활성화 했을 경우의 수들 중에서 비용의 최소값을 구해야 합니다. 문제를 그대로 받아들이고 해결하려 한다면 상당히 어렵습니다. 문제를 재정의 해보죠. 메모리의 관점이 아닌 비용의 관점으로 생각해봅시다. 그렇다면 발생할 수 있는 상황들을 비용이 K 일때 확보할 수 있는 메..

배낭 문제 N 개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지고, 해당 물건을 배낭에 넣으면 V 만큼의 가치를 얻는다. 최대 K 만큼의 무게만을 넣을 수 있는 배낭이 있을 때, 배낭에 넣을 수 있는 물건들의 가치의 최대값을 구하여라. 위의 문제가 배낭 문제 입니다. 문제의 상황이나 디테일한 부분은 달라질 수 있겠지만 대게 가중치 W 와 값 V 가 주어지고 가중치의 합이 K를 넘지 않도록 물건들을 조합하여 V의 합이 최대가 되도록 구하는 문제로 정의할 수 있습니다. Fractional Knapsack Problem 주어진 물건들이 분할 가능한 경우입니다. 물건들이 분할 가능하기 때문에 무게당 가치를 계산하여 높은 순서대로 배낭에 넣으면 K 까지 넣었을 때의 가치가 최대값 입니다. 즉, 그리디 알고..