Demostrar que un algoritmo codicioso selecciona el máximo número de programas

Question

Esto es un problema de deberes. Intuitivamente, sé que es cierto, porque el mayor grupo de programas (digamos, $j$ programas) deben estar compuestos por el menor $j$ programas. Pero, ¿cómo hacer para demostrarlo formalmente? Si alguien pudiera indicarme la dirección correcta, sería estupendo.

Planteamiento del problema:

Dejemos que $P_1, P_2, ..., P_n$ sea $n$ programas que se almacenan en un disco con capacidad $D$ megabytes. Programa $P_i$ requiere $s_i$ megabytes de almacenamiento. No podemos almacenarlos todos porque $D < \sum_{i=1}^n s_i$ .\

¿Un algoritmo codicioso que selecciona los programas en orden no decreciente $s_i$ maximizar el número de programas que contiene el disco? Demuestra o da un contraejemplo.

Answer 1

Este algoritmo sí maximiza el número de programas en el disco. Como hay un número finito de combinaciones de programas para elegir, sabemos que el máximo existe. Supongamos que $M$ es el conjunto de programas en el disco que maximiza el número de programas en el disco. Si $P_i\notin M$ y $s_i \lt s_j$ para algunos $P_j\in M$ podemos sustituir $P_j$ con $P_i$ y el número de programas es el mismo. Podemos continuar este proceso hasta que no haya más $P_i$ .

Answer 2

Sin pérdida de generalidad, supongamos que $s_1 \leq s_2 \leq s_3 \leq \cdots \leq s_n$ . Que el algoritmo codicioso elija el primer $m$ programa $P_1,P_2,\ldots,P_m$ . El espacio ocupado por el algoritmo codicioso es $$S_{\text{greedy}} = P_1 + P_2 + \cdots + P_m$$ Por lo tanto, tenemos que $$P_1 + P_2 + \cdots + P_m + P_{m+1} > D \tag{$ \N - La estrella $}$$ Dejemos que otro algoritmo elija $l$ programas, donde $l \geq m+1$ . Que estos programas sean $P_{a(1)},P_{a(2)}, \ldots, P_{a(l)}$ , donde $a(k)$ son distintos y forman una secuencia creciente. El espacio ocupado por estos programas es $$S_{\text{algorithm}} = P_{a(1)} + P_{a(2)} + \cdots + P_{a(l)}$$

Ahora bien, tenga en cuenta que como $a(k)$ es una secuencia creciente, tenemos $$a(k) \geq k \implies P_{a(k)} \geq P_k\tag{$ \N - La página web de la empresa. $}$$ Por lo tanto, obtenemos que $$S_{\text{algorithm}} \geq P_1 + P_2 + \cdots + P_l = \underbrace{P_1 + \cdots + P_m + P_{m+1}}_{>D} + \sum_{k=m+2}^l P_k \,\,\,\,\,\,\,\,\,(\because l \geq m+1)$$ Contradicción. Por lo tanto, $l \leq m$ . $(\star)$ y $(\perp)$ son los ingredientes cruciales.