The Oracle (tm) Users' Co-Operative FAQ

How do I solve a “Bin Fitting “problem in an SQL statement?


Author's name: Frank Zhou

Author's Email:zhou328@comcast.net

Date written: 18th November 2006

Oracle version(s): 10.2

How do I solve a “Bin Fitting” problem in a SQL Statement

Back to index of questions


The following SQL Model Clause Pattern can be used to solve problems relating to distributing items as evenly as possible for a predetermined number of buckets. Here is an example for distributing items in three buckets:

create table t (

   item_name varchar2(8)  not null, 

   item_value number(8) not null 

   )

 

insert into t

select 'item'||n, 100+n*decode(mod(n,2),1,1,-1) from 

(select level n from dual connect by level <13)

Commit

 

SELECT item_name name, item_value value,

       bucket_name, sum(bucket_1) OVER (ORDER BY rn) b1,

         sum(bucket_2) OVER (ORDER BY rn) b2,

         sum(bucket_3) OVER (ORDER BY rn) b3

 FROM

 (SELECT item_name, item_value, bucket_name, rn, bucket_1, bucket_2, bucket_3 FROM

   (SELECT item_name, item_value, count(*) OVER ( ) counter,

           row_NUMBER() OVER (ORDER BY item_value desc) rn FROM t)

 MODEL

 DIMENSION BY (rn)

 MEASURES (item_name, item_value, 0 it, counter,

 CAST(NULL AS NUMBER) bucket_name, CAST(NULL AS NUMBER) min_tmp,

 CAST(NULL AS NUMBER) bucket_1,    CAST(NULL AS NUMBER) bucket_2, 

 CAST(NULL AS NUMBER) bucket_3,    CAST(NULL AS NUMBER) pbucket_1,  

 CAST(NULL AS NUMBER) pbucket_2,   CAST(NULL AS NUMBER) pbucket_3

 )

 RULES ITERATE (10000)

 UNTIL (ITERATION_NUMBER>= counter[1])

 (

 

 pbucket_1[2] = CASE WHEN it[ITERATION_NUMBER] = 0 THEN 0 END ,

 pbucket_2[2] = CASE WHEN it[ITERATION_NUMBER] = 0 THEN 0.00001 END ,

 pbucket_3[2] = CASE WHEN it[ITERATION_NUMBER] = 0 THEN 0.00002 END ,

  min_tmp[1] = least(sum(pbucket_1)[ANY], sum(pbucket_2)[ANY], sum(pbucket_3)[ANY]) ,

bucket_1[ITERATION_NUMBER] = CASE WHEN sum(pbucket_1)[ANY] = min_tmp[1]

                                   THEN item_value[ITERATION_NUMBER]  END,

 bucket_2[ITERATION_NUMBER] = CASE WHEN sum(pbucket_2)[ANY] =  min_tmp[1]

                                   THEN item_value[ITERATION_NUMBER]  END,

 bucket_3[ITERATION_NUMBER] = CASE WHEN sum(pbucket_3)[ANY] =  min_tmp[1]

                                   THEN item_value[ITERATION_NUMBER]  END,

bucket_name[ITERATION_NUMBER] =CASE WHEN sum(pbucket_1)[ANY] = min_tmp[1] THEN 1

                                    WHEN sum(pbucket_2)[ANY] = min_tmp[1] THEN 2

                                    WHEN sum(pbucket_3)[ANY] = min_tmp[1] THEN 3 

                                           END,                        

pbucket_1[1] = sum(bucket_1)[ANY],

pbucket_2[1] = sum(bucket_2)[ANY],

pbucket_3[1] = sum(bucket_3)[ANY]   ,

it[ITERATION_NUMBER] = ITERATION_NUMBER 

 )                 

)

WHERE item_name IS NOT NULL

ORDER BY rn; 

 

 

NAME          VALUE BUCKET_NAME         B1         B2         B3               

-------- ---------- ----------- ---------- ---------- ----------               

item11          111           1        111                                     

item9           109           2        111        109                          

item7           107           3        111        109        107               

item5           105           3        111        109        212               

item3           103           2        111        212        212               

item1           101           1        212        212        212               

item2            98           1        310        212        212               

item4            96           2        310        308        212               

item6            94           3        310        308        306               

item8            92           3        310        308        398               

item10           90           2        310        398        398               

 

NAME          VALUE BUCKET_NAME         B1         B2         B3               

-------- ---------- ----------- ---------- ---------- ----------               

item12           88           1        398        398        398               

 

12 rows selected.

 

SQL> spool off

 

 

Back to top

Back to index of questions