[알고리즘] 그리디 알고리즘 - 배낭 문제

<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>

---

배낭 문제

개요

　배낭 문제(knapsack problem)는 조합 최적화의 한 부분으로, 최적화 이론 및 적용을 이해하는데 근본적인 문제다. 즉, 이 문제는 제한된 무게(또는 부피)의 배낭에 가장 가치 있는 물품들을 적절히 담는 방법을 찾는 것이다. 여기서 물건들은 각각 특정한 무게와 가치를 갖는다.

---

본문

 

　배낭 문제는 주로 0-1 배낭 문제와 분할 가능 배낭 문제 두 가지 유형으로 분류된다. 일반 배낭 문제라고도 불리는 0-1 배낭 문제는 각각의 아이템이 배낭에 포함되거나 포함되지 않는 두 가지 상태만을 갖는다. 따라서, 아이템을 쪼개서 담는 것이 불가능하다. 이 문제는 NP-완전 문제로 분류되어, 이를 다항 시간 내에 결정적으로 풀 수 있는 알고리즘이 알려져 있지 않다. 

 

무게가 7kg가 되게 0-1 배낭 문제를 해결

 

　반면, 분할 가능 배낭 문제는 아이템을 임의의 양으로 나눌 수 있어, 가치 대 무게 비율이 가장 높은 아이템부터 차례로 담아나가는 그리디 방식으로 풀 수 있다. 이 경우, 아이템의 일부를 선택할 수 있으므로, 쪼개어 담는 것이 가능하다. 

 

무게가 7kg가 되게 분할 가능 배낭 문제를 해결. 이때 물건 2를 분할했다는 것에 주목하자.

---

구현

　지금부터 분할 가능 배낭 문제를 그리디 방식으로 풀어보겠다.

 

#include <iostream>
#include <algorithm>
#include <vector>

struct knapsack
{
	int _id, _weight;
	double _price, _price_per_unit_weight;
};

　객체를 표현할 knapsack 구조체를 정의한다. 분할이 가능하므로 단위 무게당 가격을 나타내는 지표도 있으면 훨씬 편하게 구할 수 있다.

 

auto solution(std::vector<knapsack>& obj, int capacity)
{
	std::vector<knapsack> tmp = obj;
	obj.clear();

	std::sort(tmp.begin(), tmp.end(), [](const knapsack& k1, const knapsack& k2)
		{
			return k1._price_per_unit_weight > k2._price_per_unit_weight;
		});

　분할 가능 배낭 문제의 솔루션 함수 solution()이다. 먼저 단위 무게당 가격을 기준으로 물건들을 내림차순 정렬을 한다.

 

	int total_weight = 0;
	auto it = tmp.begin();

	while (total_weight < capacity && it != tmp.end())
	{
		obj.push_back(*it);

		total_weight += it->_weight;
		it++;
	}

　배낭 최대 용량이 될 때까지 물건을 채워 넣는다.

 

	if(total_weight - capacity > 0)
	{
		knapsack& last = obj.back();

		last._weight -= total_weight - capacity;
		last._price -= last._price_per_unit_weight * (total_weight - capacity);
	}

	return obj;
}

　만약 배낭에 넣은 물건의 무게 합이 배낭 최대 무게를 초과할 경우, 마지막에 넣은 물건을 일부 덜어내어 배낭 최대 무게에 맞도록 설정한다.

 

void print(std::vector<knapsack>& v)
{
	for (const auto& val : v)
	{
		std::cout << "[" << val._id << "] ";
		std::cout << "\tprice: " << val._price;
		std::cout << "\tweight: " << val._weight;
		std::cout << "\tprcie per unit weight: " << val._price_per_unit_weight << "\n";
	}
}

　주어진 양식에 맞게 출력하는 print() 함수다.

 

int main()
{
	std::vector<knapsack> content;
	std::vector<int> weight { 1,2,5,9,2,3,4 };
	std::vector<double> price { 10, 7, 15, 10, 12, 11 ,5 };

	for (int i = 0; i < 7; ++i)
		content.push_back({ i + 1, weight[i], price[i], price[i] / weight[i] });

	std::cout << "--------------------------------before-------------------------------\n";
	print(content);

	std::cout << "\n--------------------------------after-------------------------------\n";
	solution(content, 7);
	print(content);
}

출력 결과

 

총합본

#include <iostream>
#include <algorithm>
#include <vector>

struct knapsack
{
	int _id, _weight;
	double _price, _price_per_unit_weight;
};

auto solution(std::vector<knapsack>& obj, int capacity)
{
	std::vector<knapsack> tmp = obj;
	obj.clear();

	std::sort(tmp.begin(), tmp.end(), [](const knapsack& k1, const knapsack& k2)
		{
			return k1._price_per_unit_weight > k2._price_per_unit_weight;
		});

	int total_weight = 0;
	auto it = tmp.begin();

	while (total_weight < capacity && it != tmp.end())
	{
		obj.push_back(*it);

		total_weight += it->_weight;
		it++;
	}

	if(total_weight - capacity > 0)
	{
		knapsack& last = obj.back();

		last._weight -= total_weight - capacity;
		last._price -= last._price_per_unit_weight * (total_weight - capacity);
	}

	return obj;
}

void print(std::vector<knapsack>& v)
{
	for (const auto& val : v)
	{
		std::cout << "[" << val._id << "] ";
		std::cout << "\tprice: " << val._price;
		std::cout << "\tweight: " << val._weight;
		std::cout << "\tprcie per unit weight: " << val._price_per_unit_weight << "\n";
	}
}

int main()
{
	std::vector<knapsack> content;
	std::vector<int> weight { 1,2,5,9,2,3,4 };
	std::vector<double> price { 10, 7, 15, 10, 12, 11 ,5 };

	for (int i = 0; i < 7; ++i)
		content.push_back({ i + 1, weight[i], price[i], price[i] / weight[i] });

	std::cout << "--------------------------------before-------------------------------\n";
	print(content);

	std::cout << "\n--------------------------------after-------------------------------\n";
	solution(content, 7);
	print(content);
}

---

요약

배낭 문제
1. 정의: 주어진 무게 내에서 가장 가치가 높은 물건들을 선택하는 조합 최적화 문제
2. 종류
　a. 0-1 배낭 문제: NP-완전 문제로서, 쪼개어 담는 것이 불가능 (동적 프로그래밍 알고리즘으로 구현)
　b. 분할 가능 배낭 문제: 쪼개어 담는 것이 가능 (그리디 알고리즘으로 구현)