Você tem que limitar ao máximo o custo total, ou o número de combinações subirá ao céu, não importa como você tente encontrá-las. No exemplo a seguir, ele está limitado a 75, mas você pode tentar outros valores para ver se ainda pode encontrar resultados em um tempo razoável.
Você também pode adaptar esta solução para atualizar a tabela de combinações em inserções ou atualizações para sua tabela principal, permitindo obter resultados extremamente rápidos para qualquer intervalo que não exceda seu limite definido (mas inserções lentas obviamente, pois é onde todo o trabalho é feito).
Crie tabelas e acione:
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 ;
Em seguida, preencha usando:
INSERT INTO newparts( name, price )
SELECT part_number, cost FROM yourtable
WHERE cost <= 75;
ou (como dados de teste)
INSERT INTO newparts( name, price ) VALUES
('A012', 5),('A034', 1),('A084', 10),('A094', 25),('A233', 75),
('A343', 75),('A370', 50),('B309', 13),('C124', 78);
E, finalmente, obtenha seu resultado usando:
SELECT * FROM total_max75 WHERE total BETWEEN 70 AND 75;
Você pode colocar qualquer intervalo aqui com um máximo menor que 75 (ou o que você definir como limite na parte de criação da tabela e no gatilho).
Resultados:
A084, A370, B309 73 (you missed this one in your question)
A034, A084, A370, B309 74
A233 75
A343 75
A094, A370 75
