#
# Имеется груз массой massa и набор весов, указанных в таблице
#
#     CREATE TABLE m ( n INT UNSIGNED NOT NULL AUTO_INCREMENT, w INT NOT NULL, PRIMARY KEY(n) );
#     INSERT INTO m VALUES (NULL, 3), (NULL, 5), (NULL, 4);
#
# где n - порядковый номер веса (без разрывов), w - вес
#
# Можно ли указанными в таблице весами взвесить груз массой massa?
#
#     see http://www.youtube.com/watch?v=O97NBMlXAvc
#

DELIMITER $$

DROP FUNCTION IF EXISTS can_calc_weight$$
CREATE FUNCTION can_calc_weight (massa INT UNSIGNED)
  RETURNS INT UNSIGNED
BEGIN
  DECLARE k INT UNSIGNED;
  DECLARE max_k INT UNSIGNED;
  DECLARE RESULT INT UNSIGNED;

  INSERT INTO h VALUES (0);

  SET max_k = (SELECT MAX(n) FROM m);
  SET k = 1;

  while k <= max_k do
      INSERT INTO g SELECT DISTINCT h.i + t.w
                        FROM    h,
                            (   SELECT m.w
                                FROM m
                                WHERE n=k
                            UNION
                                SELECT -m.w
                                FROM m
                                WHERE n=k ) AS t;


      INSERT IGNORE INTO h SELECT * FROM g;
      DELETE FROM g;
      SET k = k + 1;
  END while;

  SET RESULT = IF(massa IN (SELECT h.i FROM h WHERE h.i>0), 1, 0);
  DELETE FROM h;
  RETURN RESULT;
END$$

DELIMITER ;

SET SQL_SAFE_UPDATES = 0;

# все веса, которые могут получиться из входных весов
DROP TEMPORARY TABLE IF EXISTS h;
CREATE TEMPORARY TABLE h ( i INT NOT NULL );

# веса, получаемые добавлением и вычитанием нового элемента
# из каждого элемента текущего набора.
DROP TEMPORARY TABLE IF EXISTS g;
CREATE TEMPORARY TABLE g ( i INT NOT NULL );

SELECT can_calc_weight(12), can_calc_weight(10);

DROP TEMPORARY TABLE g;
DROP TEMPORARY TABLE h;