Кража во Всемирном банке
Данный мешок вместимости W и два массива A[] и B[] длины N , где A[i] представляет вес i -го блока золота, а B[i] представляет прибыль, полученную при взятии i -го блока золота, задача состоит в том, чтобы найти максимальную прибыль, полученную при взятии части или целого слитка золота с неполным квадратным весом, не превышающим вместимость мешка.
Примеры:
Input: A[]= {4, 5, 7}, B[] = {8, 5, 4), W = 10
Output: 7.857
Explanation:
One way to obtain the maximum profit is:
- Take the whole second block, getting a profit of 5 and reducing the capacity to 5.
- Take a fraction of 5/7 of the third block, getting a profit of (5/7)*4 = 2.857 and reducing the capacity to 0.
Thus, the maximum obtained profit is equal to (5+2.857 = 7.857), which is the maximum possible.
Input: A[]= {2, 5, 3}, B[] = {7, 6, 9), W = 8
Output: 19.600
Подход: Данную задачу можно решить с помощью жадного алгоритма, известного как дробный ранец. Выполните следующие шаги, чтобы решить проблему:
- Инициализируйте вектор пар, скажем, V , чтобы сохранить пары, образованные путем взятия элементов массива из массива B[] в качестве первого элемента и элементов массива из массива B[] в качестве второго элемента, имеющего тот же индекс.
- Перебрать диапазон [0, N] и, если A[i] не является идеальным квадратом, затем вставить пару {B[i], A[i]} в вектор V .
- Отсортируйте вектор V в порядке убывания с помощью пользовательского компаратора по отношениям пар.
- Инициализируйте переменную, скажем, прибыль как 0 , чтобы сохранить максимальную прибыль.
- Пройдите вектор V и выполните следующие шаги на каждой итерации:
- Если второй элемент текущей пары меньше или равен W , то увеличить прибыль на первый элемент пары, т.е. взять весь блок золота, а затем уменьшить W на второй элемент текущей пары .
- В противном случае возьмите сумму, равную отношению W и второго элемента текущей пары , и сохраните ее в переменной P. Затем увеличивайте прибыль на P*первый элемент текущей пары, а затем ломайтесь.
- Наконец, после выполнения вышеуказанных шагов выведите полученное значение прибыли в качестве ответа.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N * log(N))
Вспомогательное пространство: O(N)