Encuentre combinaciones que cumplan con un criterio variado

Tienes que limitar el costo total máximo, o la cantidad de combinaciones se disparará sin importar cómo intentes encontrarlas. En el siguiente ejemplo, está limitado a 75, pero puede probar otros valores para ver si todavía puede encontrar resultados en un tiempo razonable.

También puede adaptar esta solución para actualizar la tabla de combinaciones en inserciones o actualizaciones para su tabla principal, lo que le permite obtener resultados extremadamente rápidos para cualquier rango que no exceda su límite establecido (pero obviamente ralentiza las inserciones, ya que es donde se hace todo el trabajo).

Crear tablas y desencadenar:

CREATE TABLE `total_max75` (
 `id` int(11) NOT NULL AUTO_INCREMENT,
 `parts` varchar(255) NOT NULL,
 `num` int(11) NOT NULL,
 `total` int(11) NOT NULL,
 PRIMARY KEY (`id`),
 KEY `total` (`total`,`num`)
); 

CREATE TABLE `newparts` (
 `name` char(4) NOT NULL,
 `price` int(11) NOT NULL,
 PRIMARY KEY (`name`)
);

DELIMITER //
CREATE TRIGGER addtotal AFTER INSERT ON newparts
FOR EACH ROW
BEGIN
IF NEW.price <= 75 THEN
   INSERT INTO total_max75 ( parts, num, total )
     SELECT CONCAT( t.parts, ', ', NEW.name), 
       t.num+1, t.total+NEW.price 
   FROM total_max75 t
   WHERE t.total <= 75 - NEW.price AND num < 40;

   INSERT INTO total_max75( parts, num, total )
     VALUES( NEW.name, 1, NEW.price );
END IF;
END//
DELIMITER ;

Luego complete usando:

INSERT INTO newparts( name, price )
SELECT part_number, cost FROM yourtable
WHERE cost <= 75;

o (como datos de prueba)

INSERT INTO newparts( name, price ) VALUES
('A012', 5),('A034', 1),('A084', 10),('A094', 25),('A233', 75),
('A343', 75),('A370', 50),('B309', 13),('C124', 78);

Y finalmente obtenga su resultado usando:

SELECT * FROM total_max75 WHERE total BETWEEN 70 AND 75;

Puede poner cualquier rango aquí con un máximo de menos de 75 (o lo que establezca como límite en la parte de creación de la tabla y el activador).

Resultados:

A084, A370, B309        73 (you missed this one in your question)
A034, A084, A370, B309  74
A233                    75
A343                    75
A094, A370              75