Дробный ранец с использованием C++

В этой статье мы научимся решать задачу о дробном рюкзаке с помощью C++. Мы начнем с рассмотрения постановки задачи, а затем перейдем к решению. Эта задача является одной из многих популярных классических задач. Он сильно отличается от своего родного рюкзака 0-1 и рюкзака 0-N. Это жадный алгоритм, а два других — алгоритмы динамического программирования.

Что такое дробный рюкзак?

Вам дан список веса и цен на определенные предметы и сумка/рюкзак определенной вместимости, скажем W. Ваша задача – заполнить эту сумку таким образом, чтобы общая стоимость всех предметов, которые вы берете в этом сумка максимальная для всех комплектаций. И вы можете собрать любой объект целиком или его часть.

Дробный алгоритм рюкзака

Хорошо, давайте посмотрим на алгоритм решения этой задачи. Поскольку мы будем реализовывать жадное решение этой проблемы, ниже приводится краткое описание жадных алгоритмов.

Что такое жадный алгоритм?

В этих алгоритмах мы стремимся достичь локального максимума/минимума на каждом шаге, чтобы в итоге достичь глобального максимума/минимума. То есть мы максимизируем/минимизируем ответ на каждую из подзадач, и это приводит нас к максимальному/минимальному ответу общей задачи.

Примечание: Жадный выбор, который вы собираетесь сделать, должен быть безопасным.

Безопасный ход: Ход называется безопасным, если существует оптимальный ответ, надежный для этого начального хода.

Стратегия работы с жадными алгоритмами

Ниже приведены шаги, которые вы должны выполнить, чтобы разработать идеальный жадный алгоритм.

• Сделайте жадный выбор
• Докажите, что это безопасный ход, чтобы вы не писали код и в конце не обнаружили, что это был невозможный выбор. Этот конкретный шаг является наиболее важным в жадных алгоритмах.
• Свести к меньшей проблеме
• Решите все мелкие проблемы.

Псевдокод

Теперь мы шаг за шагом пройдем алгоритм рюкзака.

• Отсортируйте элементы в порядке убывания соотношения стоимости и веса. Только этот шаг снижает временную сложность выбора лучшего элемента с O(N) до O(log2N).
• Теперь мы начинаем выбирать объекты, запуская цикл for от i=0 до i=N
• Лемма: Существует оптимальное решение, которое использует как можно больше предметов с максимальным значением на единицу веса.
  • Доказательство: попробуйте заполнить рюкзак по другому критерию выбора, вы всегда получите меньшую общую сумму, чем максимально возможная.

  Приведенный ниже пример доказывает, что наша лемма верна.

  • Теперь, если размер предмета с максимальным соотношением цена/вес соответствует размеру рюкзака, возьмите его целиком. В противном случае возьмите максимально возможную долю.
  • Уменьшите вместимость сумки на вес взятого предмета.
    • Если предмет взят целиком, то: вместимость=вместимость - вес[this_item].
    • В противном случае вместимость становится равной 0, поскольку рюкзак заполняется.
    • Если товар взят целиком: total_value += value[this_item]
    • В противном случае значение += Fraction_of_weight_taken * значение[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;
    }
    

    Выход

    Заключение

    Дробный рюкзак — это жадный алгоритм, и в этой статье мы рассмотрели его реализацию. Мы вкратце узнали о жадных алгоритмах, затем обсудили псевдокод алгоритма дробного ранца. Мы доказали, что наш жадный выбор — безопасный ход, и в конце концов написали программу на C++, чтобы продемонстрировать это решение. Общая временная сложность этой концепции составляет: O(Nlog2N). На сегодня все, спасибо за прочтение.

    Дальнейшее чтение

    Если вы хотите узнать больше о рюкзаке и других жадных алгоритмах, вы можете обратиться к следующим веб-сайтам.