Editorial for Computación en la nube

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

La versión más fácil posible

$F_i = 1, f_i = 1$ ~F_i = 1, f_i = 1~ $C_i = 1, c_i = 1$ ~C_i = 1, c_i = 1~ $n = 1$ ~n = 1~ (una máquina)

(considerar el orden más rentable)

Versión estándar

$F_i = 1, f_i = 1$ ~F_i = 1, f_i = 1~ $C_i = 1, c_i = 1$ ~C_i = 1, c_i = 1~

$n = 1$ ~n = 1~ (una máquina)

$O(m×c_1)$

dp [cores] - el mayor beneficio de tener tantos cores

Doble version

$F_i = 1, f_i = 1$ ~F_i = 1, f_i = 1~

$C_i = 1, c_i = 1$ ~C_i = 1, c_i = 1~

n = 1 (una máquina)

dos mochilas

$O(n × (n × C) + m × (m × C))$

Doble version

$F_i \le f_i$ ~F_i \le f_i~ ← también funciona

$C_i = 1, c_i = 1$ ~C_i = 1, c_i = 1~

$n = 1$ ~n = 1~ (una máquina)

dos mochilas

$O (n × (n × C) + m × (m × C))$

Una mochila con artículos modificados, por ejemplo:

Una tarea con peso 5 y valor 20.
Una máquina con peso -7 y valor -15.

Debemos terminar con peso total 0 o menor.

$O ((n + m) × (n × C))$

Ordenar por $f_i, F_i$ ~f_i, F_i~ decrecientemente.

Entonces solo garantizamos que el peso total es 0 o más pequeño en cada momento del tiempo.

$O ((n + m) × (n × C))$

La mochila alternativa.

$V_i = 1, v_i = 1$ ~V_i = 1, v_i = 1~

dp [cores] → dp [dinero]

$O ((n + m) × n)$

Comments

There are no comments at the moment.