Cómo resolver el problema de la mochila de la computadora usando Excel

Cualquiera que sepa de informática sabe que el problema de la mochila es uno de los problemas matemáticos más difíciles de resolver para las computadoras. El llamado problema de la mochila es una metáfora vívida: alguien tiene una mochila y una cantidad conocida de artículos. La mochila sólo puede contener un peso limitado y cada artículo tiene un peso diferente. Cómo combinar artículos para que se ajusten al peso designado de la mochila. (Además, la maximización del valor analizada en el problema de la mochila no se analizará aquí).

El problema también puede ser: el personal financiero necesita encontrar una cantidad de facturas en una pila de facturas que sumen a un valor. Especifique el valor. Si este problema se puede resolver rápidamente, la eficiencia del trabajo mejorará enormemente.

Algunas personas dicen que pueden simplemente tomar algunas facturas al azar, sumar los montos y probar unas cuantas veces más. (Término profesional método de retroceso)

Algunas personas dicen que es posible combinar todos los montos de factura posibles y resolver cada combinación primero para seleccionar el resultado correcto, ¿verdad? (Término profesional método recursivo)

Este problema parece simple, pero no lo es.

El siguiente es un pequeño ejemplo para analizar los principios y dificultades matemáticas:

La empresa A emitió nueve facturas al cliente Empresa B y solicitó el cobro. El importe de estas nueve facturas son. 1521 yuanes, 1314 yuanes, 559 yuanes, 2120 yuanes, 5602 yuanes, 498 yuanes, 1120 yuanes y 379 yuanes respectivamente. El cliente solo llamó 6.075 yuanes debido a problemas financieros. Dado que el personal relevante del cliente estaba en un viaje de negocios y no pudo ser contactado, la Compañía A tuvo que calcular sus propias finanzas: ¿Qué facturas representan la suma de 6.075 yuanes?

El principio matemático es muy sencillo: ordena y combina todas las facturas y calcula el resultado de todas las combinaciones. Es decir, encontrar todos los subconjuntos de una matriz.

Hay nueve facturas en este caso, y cada factura tiene dos estados durante el proceso de combinación: no combinada y combinada. Estos dos estados están representados por 0 y 1. En otras palabras, podemos usar binario para representarlo, entonces el estado combinado de 9 facturas está en el rango de 000000000-111111111.

111111111 en binario es igual a 511 en decimal. En otras palabras, es posible que el personal financiero tenga que probar hasta 511 veces antes de poder obtener el resultado.

¿Qué pasa si hay diez facturas? La respuesta es 1023 veces. ¿Qué pasa si hay once facturas? La respuesta es 2047 veces.

¿Qué pasa si hay dieciséis facturas? La respuesta es 65535 veces. ¡Esta es definitivamente una carga de trabajo que no puedes imaginar! Mucha gente en Internet ha hecho esta pregunta en la Ayuda EXECL, pero no he encontrado la respuesta correcta. Muchos internautas dicen que este problema se puede resolver con Solver. Después de practicar, descubrí que esta respuesta es completamente engañosa. (La resolución es entre unos pocos números específicos, mientras que el problema de la mochila es un número indefinido)

Entonces, me tomó dos días pensar en la solución más simple: (Incluso pensé en usar lenguaje C o Programación VBS para resolver el problema, pero lo dejé decididamente porque todavía era demasiado problemático)

Permítanme hablar sobre cómo usar EXCEL para resolver este problema.

Debido a limitaciones de espacio, tomo cuatro facturas como ejemplo. Los montos de la factura son 13206, 6542, 7862 y 6321 respectivamente, y se especifica un valor de suma de 27389 como nuestro objetivo.