| selecting a best combination of numbers from a list of numbers [message #281617] |
Sun, 18 November 2007 17:20  |
dews
Messages: 7
Registered: November 2007
|
Junior Member |
|
|
I would be greatful if anyone can help me in the following
I want to extract 3 or lesser numbers whose sum is 25 (if not then nearest to 25) from a varying list of numbers.
As an example following is the list of numbers
10, 12, 4 , 5 (In some case i will have only one number in the list and in some other case it might be upto 10)
I should get a list of three numbers as follows
10, 12
[Updated on: Sun, 18 November 2007 23:01] Report message to a moderator |
|
|
|
|
|
| Re: selecting a best combination of numbers from a list of numbers [message #281619 is a reply to message #281618] |
Sun, 18 November 2007 18:03  |
dews
Messages: 7
Registered: November 2007
|
Junior Member |
|
|
Hi,
Thanks for giving an immediate response.
I am looking forward for a PL/SQL program for doing this. I have lot of products for sale in different category.
I need to rollout an offer for customers where customers can pick up three or lesser products upto USD 25 from each category.
example
product category name price
book-1 books&periodicals 10
book-2 " 3
book-3 " 4
book-4 " 12
similarly different products under different category.
I am looking for your help in selecting three or lesser products whose sum is 25 from this products details table.
[Updated on: Sun, 18 November 2007 23:01] Report message to a moderator |
|
|
|
|
|
|
|
| Re: selecting a best combination of numbers from a list of numbers [message #281623 is a reply to message #281617] |
Sun, 18 November 2007 18:36 |
dews
Messages: 7
Registered: November 2007
|
Junior Member |
|
|
For better clarification i described my problem as follows (Please ignore my previous posts with the same subject). Can anyone help me to resolve this?
I have a table product_details which contains the columns category, product and price. Some sample records are as follows.
"books&periodicals","book-1",10
"books&periodicals","book-2",4
"books&periodicals","book-3",5
"books&periodicals","book-4",12
"Kitchen Utensils","Frying Pan",25
"Kitchen Utensils","Knife set",10
"Electricals","Iron Box",10
"Electricals","Bulb",12
I am trying to write a pl/sql block to retrieve a result set which satisfies the following criteria
1. From each category products up to a total of price 25. If not a better combination of products whose total value comes closer to 25
2. Number of products from each category should not exceed 3
3. Number of products in each category can vary.
After applying these critearia, result set for the given sample would be as follows
"books&periodicals","book-1",10
"books&periodicals","book-4",12
"Kitchen Utensils","Frying Pan",25
"Electricals","Iron Box",10
"Electricals","Bulb",12
Since there are indefinite products in each category, i am struggling to write a code for this.
[Updated on: Sun, 18 November 2007 23:00] Report message to a moderator |
|
|
|
| Re: selecting a best combination of numbers from a list of numbers [message #281625 is a reply to message #281623] |
Sun, 18 November 2007 19:19 |
rleishman
Messages: 3728
Registered: October 2005
Location: Melbourne, Australia
|
Senior Member |
|
|
I think you actually have two problems:
1) Think of an algorithm to get what you want.
2) Code that algorithm in PL/SQL
The second bit is easy for anyone with a bit of PL/SQL experience, providing you have already solved the first bit.
There are a number of quick-and-dirty ways that an amateur mathematician/logician like myself could solve this, but inevitably it would be hokey and non-scalable (so I'm not even going to try).
This looks a bit like a problem that I read about in a popular science book, although that was a logistics problem where you had to source N units of a certain product from any combination of known warehouses with known inventories of the product and known transport costs, and minimise the cost. There is a mathematical way to solve these types of problem, but its too complex to describe here, and besides - I don't even remember how to do it.
Of course, it also has similarities to the "Travelling Salesman Problem", for which there is no solution other than "brute force". If that were the case, then you would be justified in writing a simple PL/SQL routine that caculated EVERY combination of products, sorted them by cost, and discarded the ones over the threshold. Whoever is asking you to do this should be made to understand that this type of solution scales exponentially and would almost certainly bring your server to its knees.
I suggest you consult a mathematician in order to obtain an algorithm, then worry about coding it.
Ross Leishman
|
|
|
|
| Re: selecting a best combination of numbers from a list of numbers [message #281656 is a reply to message #281625] |
Sun, 18 November 2007 23:46 |
sundha
Messages: 6
Registered: November 2007
|
Junior Member |
|
|
Hi,
You can use the following query for your requirement
SELECT * FROM
(SELECT categories,product,price,SUM(price) OVER (PARTITION BY categories ORDER BY price ROWS 2 PRECEDING ) total_price FROM
(SELECT categories,product,price,row_number() OVER (PARTITION BY categories ORDER BY price) row_num
FROM product_details
WHERE price <26)
WHERE row_num < 4)
WHERE total_price < 26
If you have any problem with this query kindly let me know
Sundari
|
|
|
|
|
|
|
|
| Re: selecting a best combination of numbers from a list of numbers [message #281697 is a reply to message #281617] |
Mon, 19 November 2007 01:05 |
 |
rajavu1
Messages: 1574
Registered: May 2005
Location: Bangalore , India
|
Senior Member |
|
|
Hi Sundari,
Thats what I am telling OP (Not me ) Need to build a Logic/Algorithm.
In case of 10,11,15 and say two more Prices 23 and 2 ).
Your query will return 10,11 when there is One better combination of 10,15 exists .
For your question , let me give you my combination 10 and 15
(out of 10,11,15) Just try 
Rajuvan.
|
|
|
|
|
|
|
|
| Re: selecting a best combination of numbers from a list of numbers [message #282075 is a reply to message #281617] |
Tue, 20 November 2007 15:27 |
dews
Messages: 7
Registered: November 2007
|
Junior Member |
|
|
I was looking for a better solution where i can achieve this with less lines of code. I wrote a lengthy pl/sql code where i stored all combinations of numbers and thier sum in a different array. At the end i check at the resultant array and picked the best cobination.
Thanks for your kind suggestions.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Re: selecting a best combination of numbers from a list of numbers [message #285095 is a reply to message #282190] |
Mon, 03 December 2007 06:55 |
sundha
Messages: 6
Registered: November 2007
|
Junior Member |
|
|
Hi,
You can use the following queries for your requirement. I hope the product is not duplicated within a category.
I assume the total price should be less than or equal to 25, then you can use the following query
SELECT * FROM ( SELECT a.categories, a.combo,SUM(b.PRICE) tot_price,COUNT(PRODUCT),rank () OVER (PARTITION BY a.categories ORDER BY SUM(b.PRICE) DESC) price_rank
FROM (SELECT categories, SYS_CONNECT_BY_PATH (PRODUCT, '#') || '#' combo FROM PRODUCT_DETAILS
CONNECT BY PRIOR categories = categories AND PRODUCT > PRIOR PRODUCT) a, PRODUCT_DETAILS b WHERE b.categories = a.categories AND INSTR (a.combo, '#' || b.PRODUCT || '#') > 0
GROUP BY a.categories, a.combo HAVING SUM (b.PRICE) <= 25
AND COUNT(PRODUCT) <=3 ) WHERE price_rank = 1
With Regards,
Sundari
|
|
|
|
|
|
|
|
] 
Blog
Search
Help
Members
Register
Login
Home
)
