Supongamos que tenemos M monedas y queremos invertirlas en acciones. Hay N acciones en las que puede invertir una cantidad entera no negativa. El beneficio de la acción i viene dado por una función cuadrática:
AiXi2 + BiXi
donde Xi es una cantidad entera de dinero invertida en la acción i. (−1000 ≤ Ai ≤ −1) & (1 ≤ Bi ≤ 1000)
¿Diseñar un algoritmo codicioso para encontrar la cantidad máxima de dinero que podemos ganar?
No está permitido invertir una fracción de dinero en una acción. Podemos invertir menos de M monedas.
¿Sabes qué es gree?¿Cuál es el algoritmo? ¿Has intentado implementarlo? Muestra tus esfuerzos.
MBo
27 de marzo de 2021 a las 5:10
@MBo De hecho, probé el caso en el que las restricciones son opuestas, es decir, (1<Ai<1000) & (-1000
–usuario15485733
27 de marzo de 2021 a las 5:16
El pico de esa cuadrática está en x = -B / 2A
- usuario3386109
27 de marzo de 2021 a las 6:07
@user3386109 Por favor, explíquelo. Sí, la función cuadrática alcanzará su valor extremo en X = -B/2A. ¿Debo ordenar los valores A y B de acuerdo con esto en orden decreciente y luego invertir monedas en ese orden? Wisconsin¿Funcionará entonces?
–
usuario15485733
27 de marzo de 2021 a las 6:13
@ManavChhibber Por favor, arroja algo de luz sobre esto. ¡Muchas gracias!
–
usuario15485733
27 de marzo de 2021 a las 7:01
------------------------------------
Un algoritmo codicioso proporciona la mejor solución en tal caso.
El punto es que, si para una determinada acción ya se han invertido x monedas, entonces la ganancia esperada para la próxima inversión es igual a:
next_gain = f(x+1) - f(x) = 2ax + a + b
Como a es negativo, esta ganancia siempre disminuye con x, el número de monedas ya invertidas. Para ser pedante, la función de ganancia es cóncava.
Entonces se puede demostrar fácilmente que la solución óptima se obtiene gastando las monedas una por una, buscando la acción con la máxima ganancia siguiente. Esto se puede implementar con max_heap, lo que lleva a una complejidad O(M logN).
Si Mis es muy grande, entonces deberían preverse otras soluciones, por ejemplo basadas en una función lagrangiana. En este caso estarían involucradas más matemáticas. Como mencionaste que estás buscando una solución codiciosa, supuse que esta solución codiciosa es lo suficientemente rápida.
Aquí está el código en C++. Debería ser fácil de traducir a cualquier código que tenga un montón máximo.
Salida:
Profit = 16
#include <iostream>
#include <vector>
#include <queue>
struct Stock {
int index;
int n_bought;
int next_gain;
Stock (int i, int n, int gain) : index(i), n_bought(n), next_gain (gain) {};
friend operator< (const Stock& x, const Stock& y) {return x.next_gain < y.next_gain;};
};
long long int profit (std::vector<int>& A, std::vector<int>& B, int M) {
int n = A.size();
if (n != B.size()) exit (1);
std::priority_queue<Stock> candidates;
for (int i = 0; i < n; ++i) {
int gain = A[i] + B[i];
if (gain > 0) candidates.emplace(Stock(i, 0, gain));
}
long long int sum = 0.0;
int coins = 0;
while ((coins < M) &&(!candidates.empty())) {
auto zebest = candidates.top();
candidates.pop();
coins++;
sum += zebest.next_gain;
zebest.n_bought++;
int i = zebest.index;
int gain = 2*A[i]*zebest.n_bought + A[i] + B[i];
if (gain > 0) {
zebest.next_gain = gain;
candidates.push (zebest);
}
}
return sum;
}
int main() {
std::vector<int> A = {-2, -1, -2};
std::vector<int> B = {3, 5, 10};
int M = 3;
auto ans = profit (A, B, M);
std::cout << "Profit = " << ans << std::endl;
return 0;
}
------------------------------------
La función dada Y = AiXi2 + BiXi es una función cuadrática.
Para las restricciones, las inversiones (−1000 ≤ Ai ≤ −1) y (1 ≤ Bi ≤ 1000) se pueden representar como parábolas como,
Observe tres cosas:
Estas parábolas tienen su máximo en el punto dado por X'i = -Bi/2Ai
Siempre debemos invertir monedas Xi de modo que 0 ≤ Xi ≤ X'i para obtener ganancias.
Para un número determinado de monedas k, es mejor invertirlas en la inversión con máximos mayores.
El algoritmo codicioso es entonces,
Itere sobre todas las N inversiones y para cada una encuentro su correspondiente Xi = piso (X'i).
Tome todas esas inversiones k con avidezly(inversión con Xi máximo primero) tal que Sum(Xi) ≤ M para todos los i tomados.
Aquí tienes un pseudocódigo para empezar,
FIND_MAX(A, B, N, M):
allProfits = [[]]
for i = 1 to N:
profit = []
X = floor((-B[i]) / (2 * A[i]))
profit.coins = X
profit.index = i
allProfits[i] = profit
Sort(allProfits)
maxProfit = 0
for j = N downto 1:
if(M <= 0):
break
coins = min(allProfits[j].coins, M)
i = allProfits[j].index
maxProfit += (A[i] * coins * coins) + (B[i] * coins)
M -= coins
return maxProfit
5
Si X_i no es un número entero, debes redondear (X_i)
- usuario3386109
27 de marzo de 2021 a las 6:40
@user3386109 sí, por eso estoy tomando la palabra (X'i)
- Manav Chhibber
27 de marzo de 2021 a las 6:41
@ManavChhibber ¿No debería X = piso((-B[i]) / (2 * A[i]))?
–
usuario15485733
27 de marzo de 2021 a las 6:48
@ManavChhibber A1 = 2, B1 = 3 A2 = -1,B2 = 5 A3 = -2,B3 = 10 M = 3 Entonces, deberíamos obtener 16 como solución óptima pero en ten su caso solo devuelve 12.
–
usuario15485733
27/03/2021 a las 7:00
@NadirAli, sí, parece que siempre estamos buscando el máximo de monedas que deberíamos tomar tanto como podamos. Modificando la respuesta.
- Manav Chhibber
27 de marzo de 2021 a las 7:51
