View difference between Paste ID: 2kDxDbgj and p1eHfYuV

-#
+#
-# Имеется груз массой massa и набор весов, указанных в таблице
+# Имеется груз массой massa и набор весов, указанных в таблице
-#
+#
-#     create table m ( n int unsigned not null auto_increment, value int not null, primary key(n) );
+#     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 - порядковый номер веса (без разрывов),
+#
-#     value - вес
+# где n - порядковый номер веса (без разрывов), w - вес
-#
+#
-# Можно ли указанными в таблице весами взвесить груз массой massa?
+# Можно ли указанными в таблице весами взвесить груз массой massa?
-#
+#
-#     see http://www.youtube.com/watch?v=O97NBMlXAvc
+#     see http://www.youtube.com/watch?v=O97NBMlXAvc
-#
+#
-
+
-DELIMITER $$
+DELIMITER $$
-
+
-DROP function IF EXISTS can_calc_weight$$
+DROP function IF EXISTS can_calc_weight$$
-CREATE function can_calc_weight (massa INT UNSIGNED)
+CREATE function can_calc_weight (massa INT UNSIGNED)
-  RETURNS INT UNSIGNED
+  RETURNS INT UNSIGNED
-BEGIN
+BEGIN
-  DECLARE k INT UNSIGNED;
+  DECLARE k INT UNSIGNED;
-  DECLARE max_k INT UNSIGNED;
+  DECLARE max_k INT UNSIGNED;
-  DECLARE result INT UNSIGNED;
+  DECLARE result INT UNSIGNED;
-
+
-  insert into h values (0);
+  insert into h values (0);
-
+
-  set max_k = (select max(n) from m);
+  set max_k = (select max(n) from m);
-  set k = 1;
+  set k = 1;
-
+
-  while k <= max_k do
+  while k <= max_k do
-      insert into g select DISTINCT h.i + t.value
+      insert into g select DISTINCT h.i + t.w
-                        from    h,
+                        from    h,
-                            (   select m.value
+                            (   select m.w
-                                from m
+                                from m
-                                where n=k
+                                where n=k
-                            union
+                            union
-                                select -m.value
+                                select -m.w
-                                from m
+                                from m
-                                where n=k ) as t;
+                                where n=k ) as t;
-
+
-
+
-      insert ignore into h select * from g;
+      insert ignore into h select * from g;
-      DELETE FROM g;
+      DELETE FROM g;
-      set k = k + 1;
+      set k = k + 1;
-  end while;
+  end while;
-
+
-  set result = IF(massa IN (select h.i from h where h.i>0), 1, 0);
+  set result = IF(massa IN (select h.i from h where h.i>0), 1, 0);
-  DELETE FROM h;
+  DELETE FROM h;
-  RETURN result;
+  RETURN result;
-END$$
+END$$
-
+
-DELIMITER ;
+DELIMITER ;
-
+
-SET SQL_SAFE_UPDATES = 0;
+SET SQL_SAFE_UPDATES = 0;
-
+
-# все веса, которые могут получиться из входных весов
+# все веса, которые могут получиться из входных весов
-drop temporary table if exists h;
+drop temporary table if exists h;
-create temporary table h ( i INT NOT NULL );
+create temporary table h ( i INT NOT NULL );
-
+
-# веса, получаемые добавлением и вычитанием нового элемента
+# веса, получаемые добавлением и вычитанием нового элемента
-# из каждого элемента текущего набора.
+# из каждого элемента текущего набора.
-drop temporary table if exists g;
+drop temporary table if exists g;
-create temporary table g ( i INT NOT NULL );
+create temporary table g ( i INT NOT NULL );
-
+
-select can_calc_weight(12), can_calc_weight(10);
+select can_calc_weight(12), can_calc_weight(10);
-
+
-drop temporary table g;
+drop temporary table g;
 drop temporary table h;