carp please help

[mokesql]

i think you gave the right direction but its not realy the full solution. imagine that you have such a table
wfw_wps_code wfw_anteil wfw_wps_code_teil
071736.BFON 39 N/A
071736.BFON 19 N/A
071736.BFON 12 N/A
071736.BFON 9 N/A
071736.BFON 33 N/A

and i want to find out which cobmination of the rows gives me the result of sum(wfw_anteil) = 100. do you know if there is a possibility of solving it whit sql or pl/sql? thnx

kemo

 

[Kenrae]

Do you need only one combination or every combination?
Either way, I think it can't be solved using sql alone. I remember having this problem on college, studying complexity of algorithms (I still have nightmares...). It was called the Subset Sum problem. This was a NP-complete problem, which means it's very complex.
It can be solved with pl/sql, like any other algorithmical problem. You can visit

http://cse.hanyang.ac.kr/~jmchoi/class/1996-2/algorithm/classnote/node7.html

for a high-level program solution.
(go to "Approximate Knapsack and Subset Sum" and skip all the preceding theory).

But the main problem here will be the execution time of this exponential problem. How many rows will have this table? If it's large, then I think it will last too much.

 

[carp]

You may have to hit this with a recursive procedure that has five arguments - the target value, the current sum (default 0), the current level of recursion (default = 0), a list of rowids or PK values (default NULL), and the current PK value (default -1 or some other value that you know won't show up).

You will need two cursors:

one for recursive level 0, which just finds all of the rows where wfw_anteil <= your_target_value, sorted by PK value.

the other cursor will be similar to the first, but it is only going to return rows where (wfw_anteil + the current sum passed in as an argument) <= your_target_value AND PK_value > the PK value that gets passed in as an argument.

If the recursive level is 0 THEN
OPEN THE FIRST CURSOR
ELSE
OPEN THE SECOND CURSOR
END IF

For each row in the cursor:
- list_of_PK_values_or_rowids :=
list_of_PK_values_or_rowids||current_PK_or_rowid
- current_sum := current_sum + current_value;
IF (current_sum = target_value) THEN
-- print out the list of PKs/rowids
ELSIF (current_sum > target_value) THEN -- go on to next row in cursor
ELSE
-- Hit me! Increment the recursive level
and recursively call the procedure
END IF;
END;

I think this will find all of the unique combination of rows for you.

Good luck!

 

[carp]

Boy, I hate it when I see a mistake AFTER I hit the submit button!

The logic has a superfluous comparison in it. If the cursors are written correctly, current_sum + current_value can NEVER be greater than target_sum! Change the logic to:

For each row in the cursor LOOP
- list_of_PK_values_or_rowids :=
list_of_PK_values_or_rowids||current_PK_or_rowid
- current_sum := current_sum + current_value;
IF (current_sum = target_value) THEN
-- print out the list of PKs/rowids
ELSE
-- increment the recursive level value and
recursively call the procedure
END IF;
END LOOP;
END;

Also, if you open the cursor and there are no rows in it, that means there are no rows remaining that can be combined to get the desired sum, so you need to go on to the next row in the preceding recursive level. And this is the most critical part in a recursive approach - making sure you can turn off the iterations when you've gone far enough!