Hi everyone,
I am currently working on an algorithm to find the best possible combination depending on least cost to get >= the required quantity (It's very much an/similar to an unbounded KNAPSACK algorithm) . Say for example if 100 parts are required from the given pool of stores (see table data below) , i have to come up with a best possible combination. So in this example the best choice would be to pull from store_id (A, B, C ). i am currently experimenting with a record set limited to 20 which according to my approach (i.e brute force) that would be SELECT (POWER(2,20)) FROM DUAL; 1048576 * 20 iterations and it takes 30 plus seconds using pure PL/SQL . Just few more information I am performing couple of checks to see if a single store has a required qty then pick the store and exit else perform a cross join comparison ensuring that the same store_id's are not joined then finally if nothing gets me the required qty then i am going for a brute force approach. If there is a better way to short circuit the third step or any one have a similar problem and came up with a BETTER solution please let me know. It might help me and possibly many others ( SQL approach is available but not PL/SQL) . I tried looking for something similar online but was never able to find any PL/SQL implementation of Knapsack algorithm.
store_id available_qty cost_per_unit
| A | 43 | 1.93 |
| B | 34 | 2.01 |
| C | 27 | 2.12 |
| D | 24 | 2.18 |
| E | 24 | 2.18 |
| F | 24 | 2.18 |
Table script and insert statements for the above
DROP TABLE available_qty;
CREATE TABLE available_qty(store_id VARCHAR2(1) PRIMARY KEY,
available_qty NUMBER,
cost_per_unit NUMBER);
INSERT INTO available_qty(
store_id,
available_qty,
cost_per_unit)
VALUES ('A',
43,
1.93);
INSERT INTO available_qty(
store_id,
available_qty,
cost_per_unit)
VALUES ('B',
34,
2.01);
INSERT INTO available_qty(
store_id,
available_qty,
cost_per_unit)
VALUES ('C',
27,
2.12);
INSERT INTO available_qty(
store_id,
available_qty,
cost_per_unit)
VALUES ('D',
24,
2.18);
INSERT INTO available_qty(
store_id,
available_qty,
cost_per_unit)
VALUES ('E',
24,
2.18);
INSERT INTO available_qty(
store_id,
available_qty,
cost_per_unit)
VALUES ('F',
24,
2.18);
COMMIT;
Package that i implemented ( I took ideas from multiple sources and came up with this, just so everyone know)
CREATE OR REPLACE PACKAGE get_available_qty
IS
TYPE available_qty_typ IS RECORD(store_id VARCHAR2(1),
available_qty NUMBER,
cost_per_unit NUMBER,
best_combo_flag VARCHAR2(1));
TYPE available_qty_nt IS TABLE OF available_qty_typ;
TYPE available_qty_aat IS TABLE OF available_qty_typ
INDEX BY PLS_INTEGER;
FUNCTION get_best_combo(p_qty_required NUMBER)
RETURN available_qty_nt
PIPELINED;
END;
/
CREATE OR REPLACE PACKAGE BODY get_available_qty
AS
FUNCTION get_best_combo(p_qty_required NUMBER)
RETURN available_qty_nt
PIPELINED
IS
get_available_qty_nt get_available_qty.available_qty_nt
:= get_available_qty.available_qty_nt();
--Local subprogram
FUNCTION get_required_qty
RETURN available_qty_nt
IS
v_qty NUMBER := 0;
v_cost_per_unit NUMBER := 0;
v_cost_per_unit1 NUMBER := 0;
v_best_store_id VARCHAR2(4000) DEFAULT NULL;
v_best_store_id_combo VARCHAR2(4000);
is_qty_available BOOLEAN DEFAULT FALSE;
is_first_run BOOLEAN DEFAULT TRUE;
v_assign_store_id_flag DBMS_UTILITY.uncl_array;
v_table_length BINARY_INTEGER;
-- Nested local subprogram
FUNCTION return_null
RETURN available_qty_nt
IS
BEGIN
get_available_qty_nt.delete;
RETURN get_available_qty_nt;
END;
BEGIN
SELECT aq.*,
'N' best_combo_flag
BULK COLLECT INTO get_available_qty_nt
FROM available_qty aq;
FOR indx IN 1 .. get_available_qty_nt.COUNT LOOP
v_qty := v_qty + get_available_qty_nt(indx).available_qty;
END LOOP;
-- If total available qty is less than required qty then return null
IF v_qty >= p_qty_required THEN
is_qty_available := TRUE;
ELSE
get_available_qty_nt := return_null();
END IF;
--The below condition will execute when available qty >= required qty
IF is_qty_available THEN
--Check if any single store has the available qty!
FOR rec IN 1 .. get_available_qty_nt.COUNT LOOP
IF get_available_qty_nt(rec).available_qty >= p_qty_required THEN
IF (v_cost_per_unit > get_available_qty_nt(rec).cost_per_unit) THEN
v_cost_per_unit := get_available_qty_nt(rec).cost_per_unit;
v_best_store_id_combo := get_available_qty_nt(rec).store_id;
ELSIF (v_cost_per_unit = 0) THEN
v_cost_per_unit := get_available_qty_nt(rec).cost_per_unit;
v_best_store_id_combo := get_available_qty_nt(rec).store_id;
END IF;
END IF;
END LOOP;
-- Reset local variables
IF v_best_store_id_combo IS NOT NULL THEN
is_qty_available := FALSE;
ELSE
v_cost_per_unit := 0;
v_best_store_id_combo := NULL;
END IF;
--If above condition does not satisfy then perfrom a cartesian product combination comparision
IF is_qty_available THEN
FOR i IN 1 .. get_available_qty_nt.COUNT LOOP
v_qty := 0;
v_cost_per_unit1 := 0;
FOR j IN 1 .. get_available_qty_nt.COUNT LOOP
IF (get_available_qty_nt(i).store_id != get_available_qty_nt(j).store_id) THEN
v_qty := get_available_qty_nt(i).available_qty
+ get_available_qty_nt(j).available_qty;
v_cost_per_unit1 := get_available_qty_nt(i).cost_per_unit
+ get_available_qty_nt(j).cost_per_unit;
IF v_qty >= p_qty_required THEN
IF (v_cost_per_unit != 0
AND v_cost_per_unit1 < v_cost_per_unit) THEN
v_cost_per_unit := v_cost_per_unit1;
v_best_store_id_combo := get_available_qty_nt(i).store_id
|| ','
|| get_available_qty_nt(j).store_id;
ELSIF v_cost_per_unit = 0 THEN
v_cost_per_unit := v_cost_per_unit1;
v_best_store_id_combo := get_available_qty_nt(i).store_id
|| ','
|| get_available_qty_nt(j).store_id;
END IF;
END IF;
END IF;
END LOOP;
END LOOP;
-- Reset local variables
IF v_best_store_id_combo IS NOT NULL THEN
is_qty_available := FALSE;
ELSE
v_cost_per_unit := 0;
v_cost_per_unit1 := 0;
v_best_store_id_combo := NULL;
END IF;
-- Perform every possible combination(Brute Force Approach)
IF is_qty_available THEN
FOR i IN 1 .. POWER (2, get_available_qty_nt.COUNT) - 1 LOOP
v_qty := 0;
v_best_store_id := NULL;
v_cost_per_unit := 0;
FOR j IN 1..get_available_qty_nt.COUNT LOOP
IF BITAND (i, POWER(2, j - 1)) != 0 THEN
v_qty := v_qty + get_available_qty_nt(j).available_qty;
v_best_store_id := v_best_store_id || get_available_qty_nt(j).store_id || ',';
v_cost_per_unit := ( v_cost_per_unit + get_available_qty_nt(j).cost_per_unit);
END IF;
END LOOP;
IF (v_qty >= p_qty_required) THEN
IF is_first_run THEN
v_cost_per_unit1 := v_cost_per_unit;
is_first_run := FALSE;
END IF;
IF ( v_cost_per_unit <= v_cost_per_unit1 ) THEN
v_best_store_id_combo := RTRIM (v_best_store_id, ',');
v_cost_per_unit1 := v_cost_per_unit;
END IF;
END IF;
END LOOP;
END IF;
END IF;
END IF;
-- Get the list for assigning flag
DBMS_UTILITY.comma_to_table(list => v_best_store_id_combo,
tablen => v_table_length,
tab => v_assign_store_id_flag);
FOR k IN 1 .. v_assign_store_id_flag.COUNT LOOP
FOR l IN 1 .. get_available_qty_nt.COUNT LOOP
IF get_available_qty_nt(l).store_id = v_assign_store_id_flag(k) THEN
get_available_qty_nt(l).best_combo_flag := 'Y';
END IF;
END LOOP;
END LOOP;
RETURN get_available_qty_nt;
END;
BEGIN
get_available_qty_nt := get_required_qty();
FOR i IN 1 .. get_available_qty_nt.COUNT LOOP
PIPE ROW (get_available_qty_nt(i));
END LOOP;
RETURN;
END;
END get_available_qty;
-- When you call the function it returns the result set back with updated flags for stores with the most cost effective combination!
SELECT *
FROM TABLE(get_available_qty.get_best_combo(100))
ORDER BY best_combo_flag DESC;
The best stores combination for 100 items are flagged 'Y'
store_id available_qty cost_per_unit best_combo_flag
| A | 43 | 1.93 | Y |
| B | 34 | 2.01 | Y |
| C | 27 | 2.12 | Y |
| D | 24 | 2.18 | N |
| E | 24 | 2.18 | N |
| F | 24 | 2.18 | N |
SELECT *
FROM TABLE(get_available_qty.get_best_combo(70))
ORDER BY best_combo_flag DESC;
The best store combination that will make up 70 or more items are flagged 'Y'
store_id available_qty cost_per_unit best_combo_flag
| A | 43 | 1.93 | Y |
| B | 34 | 2.01 | Y |
| E | 24 | 2.18 | N |
| D | 24 | 2.18 | N |
| F | 24 | 2.18 | N |
| C | 27 | 2.12 | N |