[Algorithm/Greedy] 배낭 문제(knapsack problem)

배낭 문제

• 0-1 배낭 문제라고 부르는 일반 배낭 문제는 NP-완전 문제로 알려져 있어 다항 시간 솔루션을 사용할 수 없다.
• 하지만 문제를 조금 변경한 분할 가능 배낭 문제(fractional knapsack problem)은 그리디 방식으로 해결할 수 있다.

 

0-1 배낭 문제

• 물건들의 집합 O = [O1, O2, O3, .... , On]이 있고, 여기서 i번째 물건 Oi의 무게는 Wi이고 가격은 Vi라고 하자.
• 그리고 최대 무게를 T까지 견딜 수 있는 가방(배낭)이 하나 주어진다
• 이제 물건들을 가방에 담아야 하는데, 가방에 넣은 물건들의 가격 합이 최대가 되로록 물건을 선택해야 한다
  • 물건들의 무게 합이 T를 넘지 않아야 한다.
• 위에서 말했듯이 0-1 배낭 문제는 NP-완전 문제로 알려져 있어 다항 시간 솔루션을 사용할 수 없다.
  • 따라서 모든 가능한 조합을 조사하여 무게가 T를 넘지 않는 가장 높은 가격을 찾아내야 한다
  • 최선의 물건 조합을 찾으려면 모든 가능한 조합 목록을 만들고, 그 중 가격이 최대인 조합을 찾아야 한다.

 

분할 가능 배낭 문제

• 주어진 물건을 원하는 형태로 얼마든지 분할할 수 있고, 각 물건의 일부분만 배낭에 담을 수 있다고 가정한다
• 이 문제의 솔루션은 매우 간단하다
  • 각 물건의 단위 무게당 가격을 기준으로 정렬하고, 그리디 방식에 따라 단위 무게당 가격이 높은 순서로 물건을 선택하여 가방의 무게 T를 가득 채우면 된다.

분할 가능 배낭 문제 구현(C++)

구조체 정의

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

struct Object
{
	int id;
	int weight;
	double value;
	double value_per_unit_weight;

	Object(int i, int w, double v) : id(i), weight(w), value(v),
		value_per_unit_weight(v / w) {}

	// std::sort()에서 사용
	inline bool operator< (const Object& obj) const
	{
		return this->value_per_unit_weight < obj.value_per_unit_weight;
	}

	// 콘솔 출력 지원. std::cout << obj << std::endl; 코드 사용 가능
	friend std::ostream& operator<<(std::ostream& os, const Object& obj);
};

std::ostream& operator<<(std::ostream& os, const Object& obj)
{
	os << "[" << obj.id << "] 가격: " << obj.value 
		<< " \t무게: " << obj.weight
		<< " kg\t단위 무게 당 가격: " << obj.value_per_unit_weight;
	return os;
}

 

분할 가능 배낭 문제 알고리즘 구현 함수

참고) C++14 이후부터 deduced return type을 지원하므로, C++11이전 컴파일러를 사용하는 경우 타입을 명시해주자

// 분할가능 배낭 문제 알고리즘 구현 함수
auto fill_knapsack(std::vector<Object>& objects, int knapsack_capacity)
{
	std::vector<Object> knapsack_contents;
	knapsack_contents.reserve(objects.size());

	// 물건들을 내림차순으로 정렬 (단위 무게 당 가격 기준)
	std::sort(objects.begin(), objects.end());
	std::reverse(objects.begin(), objects.end());

	// '가장 가치있는' 물건들 먼저 배낭에 추가
	auto current_object = objects.begin();
	int current_total_weight = 0;
	while (current_total_weight < knapsack_capacity && current_object != objects.end())
	{
		knapsack_contents.push_back(*current_object);

		current_total_weight += current_object->weight;
		current_object++;
	}

	// 마지막 추가한 물건에 의해 배낭 최대 허용 무게가 초과된 경우
	int weight_of_last_obj_to_remove = current_total_weight - knapsack_capacity;
	Object& last_object = knapsack_contents.back();
	if (weight_of_last_obj_to_remove > 0)
	{
		last_object.weight -= weight_of_last_obj_to_remove;
		last_object.value -= last_object.value_per_unit_weight * weight_of_last_obj_to_remove;
	}

	return knapsack_contents;
}

 

 

테스트 코드

int main(int argc, char* argv[])
{
	std::vector<Object> objects;
	objects.reserve(7);

	std::vector<int> weights {1, 2, 5, 9, 2, 3, 4};
	std::vector<double> values {10, 7, 15, 10, 12, 11, 5};
	for (auto i = 0; i < 7; i++)
	{
		objects.push_back(Object(i + 1, weights[i], values[i]));
	}

	// 사용할 수 있는 물건 정보 출력
	std::cout << "[사용할 수 있는 물건 정보]" << std::endl;
	for (auto& o : objects)
		std::cout << o << std::endl;
	std::cout << std::endl;

	// 분할가능 배낭 문제 알고리즘 실행, 배낭의 최대 허용 무게는 7로 지정.
	int knapsack_capacity = 7;
	auto solution = fill_knapsack(objects, knapsack_capacity);

	// 배낭에 넣을 물건 정보 출력
	std::cout << "[배낭에 넣을 물건들 (최대 용량 = " << knapsack_capacity << ")]" << std::endl;
	for (auto& o : solution)
		std::cout << o << std::endl;
	std::cout << std::endl;
}

 

결과

[사용할 수 있는 물건 정보]
[1] 가격: 10    무게: 1 kg      단위 무게 당 가격: 10
[2] 가격: 7     무게: 2 kg      단위 무게 당 가격: 3.5
[3] 가격: 15    무게: 5 kg      단위 무게 당 가격: 3
[4] 가격: 10    무게: 9 kg      단위 무게 당 가격: 1.11111
[5] 가격: 12    무게: 2 kg      단위 무게 당 가격: 6
[6] 가격: 11    무게: 3 kg      단위 무게 당 가격: 3.66667
[7] 가격: 5     무게: 4 kg      단위 무게 당 가격: 1.25

[배낭에 넣을 물건들 (최대 용량 = 7)]
[1] 가격: 10    무게: 1 kg      단위 무게 당 가격: 10
[5] 가격: 12    무게: 2 kg      단위 무게 당 가격: 6
[6] 가격: 11    무게: 3 kg      단위 무게 당 가격: 3.66667
[2] 가격: 3.5   무게: 1 kg      단위 무게 당 가격: 3.5

 

Ref) 코딩 테스트를 위한 자료 구조와 알고리즘 with C++