さまざまな基準を満たす組み合わせを見つける

総コストの上限を制限する必要があります。そうしないと、どのように組み合わせを見つけようとしても、組み合わせの数が増えてしまいます。次の例では75に制限されていますが、他の値を試して、妥当な時間内に結果を見つけることができることを確認できます。

このソリューションを適応させて、メインテーブルの挿入または更新で組み合わせテーブルを更新することもできます。これにより、設定した制限を超えない範囲で非常に迅速に結果を得ることができます（ただし、すべての作業が行われる場所であるため、挿入が遅くなります）。

テーブルを作成してトリガーします：

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 ;

次に、以下を使用してデータを入力します：

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

または（テストデータとして）

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

そして最後に、以下を使用して結果を取得します：

SELECT * FROM total_max75 WHERE total BETWEEN 70 AND 75;

ここには、最大75未満（またはテーブル作成部分とトリガーで制限として設定した範囲）の範囲を指定できます。

結果：

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