Por la naturaleza binaria de tamaños, parece plausible que la codicia enfoque es óptimo.
Si que puede ser justificado, la respuesta se puede encontrar de la siguiente manera:
Deje $k$ ser máxima con $2^k\le \min\{A,B,C\}$. A continuación, utilice $\lfloor \frac A{2^k}\rfloor \cdot \lfloor \frac B{2^k}\rfloor \cdot \lfloor \frac C{2^k}\rfloor $ cajas de tamaño $2^k$. El próximo calcular el número de cajas para $(A\bmod 2^k)\times B \times C$ $(2^k\lfloor \frac A{2^k}\rfloor)\times (B\bmod 2^k)\times C$ $(2^k\lfloor \frac A{2^k}\rfloor)\times (2^k\lfloor \frac B{2^k}\rfloor)\times (C\bmod 2^k)$ y añadir. Tenga en cuenta que estos subproblemas se dispone de todos los elementos $\le 2^{k-1}$.
¿Por qué los codiciosos de aproximación trabajo? (Esto es algo informal)
Entre todas las soluciones óptimas, seleccionar uno que maximiza el número de elementos que son justificados de acuerdo a su tamaño (es decir, los vértices tienen coordenadas divisible por el elemento de lado de longitud) y entre los que seleccionar uno que prefiere cajas grandes a menor coordenadas (si se permite esta descripción informal).
Supongamos que esta se desvía de los codiciosos solución. Entonces no debe existir ambos cuadros que son más grandes y cajas que son más pequeñas que las cajas en la posición correspondiente de los codiciosos solución.
Entre tales "demasiado pequeñas" cajas, considere uno más cercano al origen. Entonces (looesly hablando) por algunos de intercambio de operaciones de uno se puede mover una caja más grande en su posición, contradiciendo la elección de este mínimo contraejemplo ...
