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

The Oracle (tm) Users' Co-Operative FAQ

How do I solve a “Bin Fitting “problem in an 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