C++를 사용한 분수형 배낭

이 기사에서는 C++를 사용하여 분수 배낭 문제를 해결하는 방법을 배웁니다. 문제 설명을 살펴보는 것으로 시작한 다음 솔루션으로 이동합니다. 이 문제는 많은 대중적인 고전 문제 중 하나입니다. 형제 0-1 배낭 및 0-N 배낭과는 상당히 다릅니다. 이것은 욕심 많은 알고리즘이고 다른 두 개는 동적 프로그래밍 알고리즘입니다.

분수 배낭이란 무엇입니까?

특정 품목의 무게와 가격 목록이 주어지고 특정 용량의 가방/배낭에 W가 표시됩니다. 귀하의 임무는 이 가방에 가져가는 모든 품목의 총 가격이 되도록 이 가방을 채우는 것입니다. 가방은 모든 구성에 대해 최대입니다. 또한 개체를 전체 또는 일부로 수집할 수 있습니다.

분수 배낭 알고리즘

자, 이 문제를 해결하기 위한 알고리즘을 살펴봅시다. 이 문제에 대한 그리디 솔루션을 구현할 것이므로 그리디 알고리즘에 대한 간략한 설명은 다음과 같습니다.

그리디 알고리즘이란 무엇입니까?

이 알고리즘에서 우리는 결국 글로벌 최대/최소를 달성하기 위해 각 단계에서 로컬 최대/최소를 달성하는 것을 목표로 합니다. 즉, 각 하위 문제에 대한 답을 최대/최소화하여 전체 문제의 최대/최소 답으로 이끕니다.

참고:당신이 하려는 탐욕스러운 선택은 안전한 이동이어야 합니다.

안전 이동: 이 초기 이동에 대해 신뢰할 수 있는 최적의 답변이 있는 경우 이동을 안전 이동이라고 합니다.

그리디 알고리즘을 사용하는 전략

다음은 완벽한 욕심쟁이 알고리즘을 개발하기 위해 따라야 하는 단계입니다.

욕심 많은 선택
안전한 이동임을 증명하여 코드를 작성하지 않고 결국 실행 가능한 선택이 아니라는 것을 알게 됩니다. 이 특정 단계는 그리디 알고리즘의 가장 중요한 단계입니다.
작은 문제로 줄이기
모든 작은 문제를 해결합니다.

의사 코드

이제 배낭 알고리즘을 단계별로 살펴보겠습니다.

가치/무게 비율 내림차순으로 항목을 정렬합니다. 이 단계만으로도 O(N)에서 O(log2N)까지 최상의 항목을 선택하는 시간 복잡도가 감소합니다.
이제 i = 0에서 i = N까지 for 루프를 실행하여 객체 선택을 시작합니다

Lemma: 무게 단위당 최대 값을 가진 항목을 최대한 많이 사용하는 최적 솔루션이 존재합니다.\n

증명: 다른 선택 기준으로 배낭을 채우면 항상 가능한 최대 값보다 작은 총 값을 얻게 됩니다.

아래에 첨부된 예는 우리의 기본형이 정확함을 증명합니다.

이제 가치/무게 비율이 최대인 물건의 크기가 배낭에 맞으면 통째로 가져갑니다. 그렇지 않으면 가능한 최대 비율을 취하십시오.

가져온 물건의 무게만큼 가방의 용량을 줄입니다.

전체 항목을 가져간 경우: 용량 = 용량 - 무게[this_item].
그렇지 않으면 배낭이 꽉 차서 용량이 0이 됩니다.

전체 항목을 가져간 경우: total_value += value[this_item]
그렇지 않으면 value += fraction_of_weight_taken * value[this_item]입니다.

의사 코드의 전체 구조는 다음과 같습니다.

분수 배낭을 시연하는 C++ 프로그램

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

using namespace std;

// this custom comparator function will allow
// us to compare our vector based on the
// ratio of values to weights
bool compare(pair <float, int> p1, pair <float, int> p2)
{
	return p1.first > p2.first;
}

int fractional_knapsack(vector <int> weights, vector <int> values, int capacity)
{
	int len = weights.size();
	int total_value = 0;

	// vector to store the items based on their value/weight ratios
	vector <pair <float, int>> ratio(len, make_pair(0.0, 0));

	for(int i = 0; i < len; i++)
		ratio[i] = make_pair(values[i]/weights[i], i);

	// now sort the ratios in non-increasing order
	// for this purpose, we will use our custom
	// comparator function
	sort(ratio.begin(), ratio.end(), compare);

	// start selecting the items
	for(int i = 0; i < len; i++)
	{
		if(capacity == 0)
			break;

		int index = ratio[i].second;

		if(weights[index] <= capacity)
		{
			// we item can fit into the knapsack
			// hence take the whole of it
			capacity -= weights[index];

			// add the value of this item to the
			// final answer
			total_value += values[index];
		}
		else
		{
			// this item doesn't fit into the bag
			// and thus we take a fraction of it
			int value_to_consider = values[index] * (float(capacity)/float(weights[index]));
			total_value += value_to_consider;
			capacity = 0;
		}
	}

	return total_value;
}

int main()
{
	cout << "Enter the weights of the items, press -1 to stop" << endl;

	vector <int> weights;

	while(true)
	{
		int weight;
		cin >> weight;

		if(weight == -1)
			break;

		weights.push_back(weight);
	}

	cout << "Enter the values of each item, press -1 to stop" << endl;
	
	vector <int> values;

	while(true)
	{
		int value;
		cin >> value;

		if(value == -1)
			break;

		values.push_back(value);
	}

	cout << "Enter the capacity of the knapsack" << endl;

	int capacity;
	cin >> capacity;

	cout << "The maximum value possible based on current list is: " << fractional_knapsack(weights, values, capacity) << endl;
}

산출

결론

fractional knapsack은 탐욕스러운 알고리즘이며 이 기사에서는 그 구현을 살펴보았습니다. 그리디 알고리즘에 대해 간단히 배운 다음 분수 배낭 알고리즘의 의사 코드에 대해 논의했습니다. 우리는 우리의 탐욕스러운 선택이 안전한 움직임이라는 것을 증명했고 결국 이 솔루션을 시연하기 위해 C++ 프로그램을 작성했습니다. 이 개념의 전체 시간 복잡도는 O(Nlog2N)입니다. 오늘은 여기까지입니다 읽어주셔서 감사합니다.

추가 자료

knapsack 및 기타 욕심 많은 알고리즘에 대해 자세히 알아보려면 다음 웹 사이트를 참조하십시오.