Consultas fraccionarias de mochila

Dada una array de enteros, que consiste en pesos positivos «W» y valores «V» respectivamente como un par y algunas consultas que consisten en un entero ‘C’ que especifica la capacidad de la mochila, encuentre el valor máximo de productos que se pueden poner en la mochila si se permite el rompimiento de objetos.

Ejemplos:

Entrada: arr[] = { {1, 2}, {1, 3}, {3, 7} }, q = {1, 2, 3, 4, 5}
Salida: {3, 5,33333, 7,66667, 10, 12}
Para ‘C’ = 1, llenaremos la mochila con elemento de valor 3.
Para ‘C’ = 2, primero llenamos con elemento de valor 3, luego 1 capacidad restante
con elemento de valor 7.
Para ‘C’ = 3, primero llenamos con elemento de valor 3, luego restantes 2 capacidades
con elemento de valor 7.
Para ‘C’ = 4, primero llenamos con elemento de valor 3, luego restantes 3 capacidades
con elemento de valor 7 Para ‘
C’ = 5, primero llenamos con elemento de valor 3, luego 3 capacidades
con elemento de valor 7 y 1 restante con elemento de valor 1.

Se recomienda que lea este artículo sobre Mochila fraccional antes de leer este artículo.

Enfoque ingenuo: un enfoque simple será clasificar la array en orden decreciente de valores V/W, es decir, la relación valor/peso. Luego, para cada consulta, iteraremos la array y sumaremos los valores enteros requeridos mientras la mochila no esté completamente llena.
Complejidad del tiempo: O(q*n*log(n))

Enfoque eficiente: las consultas se pueden optimizar realizando prefix_sum de una array ordenada tanto en peso como en valor.
A continuación se muestra el algoritmo:

1. Ordene la array por su relación Valor/Peso en orden descendente.
2. Encuentre la suma de prefijos de peso y valor respectivamente de la array.
3. Para responder una consulta:
   • Realice una búsqueda binaria para encontrar el primer elemento con prefix_sum en peso (W) mayor que ‘C’. Estrictamente hablando, busque el límite superior del valor de ‘C’ en una array prefix_sum de ‘W’. Digamos que este elemento está en un índice ‘X’.
   • Incluya la suma de los valores del índice {0, X-1} y el valor fraccionario del índice ‘X’ que se pueden acomodar en la capacidad restante.

A continuación se muestra la implementación del enfoque anterior:

// C++ program to implement above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function on the basis of which we will
// perform the sorting
bool comp(pair<int, int> a, pair<int, int> b)
{
    return (double)a.second / a.first >
                   (double)b.second / b.first;
}
  
// Function to sort the array on its value/weight
// and perform-sum on both weight and value
void preProcess(pair<int, int> arr[], int n)
{
    sort(arr, arr + n, comp);
    for (int i = 1; i < n; i++) {
        arr[i].first += arr[i - 1].first;
        arr[i].second += arr[i - 1].second;
    }
}
  
// Function to answer queries
double maxValue(int w, pair<int, int> arr[], int n)
{
    // If w is large enough
    // to cover all weights
    if (arr[n - 1].first <= w)
        return arr[n - 1].second;
  
    // Value to search on arr
    pair<int, int> search_bound = { w, INT_MAX };
  
    // Index of the item which we will put
    // partially in our knap-sack
    int x = upper_bound(arr, arr + n, search_bound) - arr;
  
    // Required value
    if (x == 0)
        return (double)w * arr[0].second / arr[0].first;
    else
        return arr[x - 1].second +
              (double)(w - arr[x - 1].first) * 
              (arr[x].second - arr[x - 1].second) /
              (arr[x].first - arr[x - 1].first);
}
  
void PrintQueries(int query[], pair<int, int> arr[],
                                        int n, int m)
{
    for (int i = 0; i < m; i += 1) {
        cout << maxValue(query[i], arr, n) << endl;
    }
}
  
// Driver code
int main()
{
    // Input array representing the data of w[] and v[]
    pair<int, int> arr[] = { { 1, 2 }, { 1, 3 }, { 3, 7 } };
    int query[5] = { 1, 2, 3, 4, 5 };
  
    // Size of the array
    int n = sizeof(arr) / sizeof(pair<int, int>);
    int m = sizeof(query) / sizeof(query[0]);
  
    // Pre-processing
    preProcess(arr, n);
  
    PrintQueries(query, arr, n, m);
  
    return 0;
}

3
5.33333
7.66667
10
12

Complejidad del tiempo: O((n+q)*log(n))