Branch data     Line data    Source code

       1                 :             : /*-------------------------------------------------------------------------
       2                 :             :  *
       3                 :             :  * knapsack.c
       4                 :             :  *        Knapsack problem solver
       5                 :             :  *
       6                 :             :  * Given input vectors of integral item weights (must be >= 0) and values
       7                 :             :  * (double >= 0), compute the set of items which produces the greatest total
       8                 :             :  * value without exceeding a specified total weight; each item is included at
       9                 :             :  * most once (this is the 0/1 knapsack problem).  Weight 0 items will always be
      10                 :             :  * included.
      11                 :             :  *
      12                 :             :  * The performance of this algorithm is pseudo-polynomial, O(nW) where W is the
      13                 :             :  * weight limit.  To use with non-integral weights or approximate solutions,
      14                 :             :  * the caller should pre-scale the input weights to a suitable range.  This
      15                 :             :  * allows approximate solutions in polynomial time (the general case of the
      16                 :             :  * exact problem is NP-hard).
      17                 :             :  *
      18                 :             :  * Copyright (c) 2017-2026, PostgreSQL Global Development Group
      19                 :             :  *
      20                 :             :  * IDENTIFICATION
      21                 :             :  *        src/backend/lib/knapsack.c
      22                 :             :  *
      23                 :             :  *-------------------------------------------------------------------------
      24                 :             :  */
      25                 :             : #include "postgres.h"
      26                 :             : 
      27                 :             : #include <limits.h>
      28                 :             : 
      29                 :             : #include "lib/knapsack.h"
      30                 :             : #include "nodes/bitmapset.h"
      31                 :             : #include "utils/memutils.h"
      32                 :             : 
      33                 :             : /*
      34                 :             :  * DiscreteKnapsack
      35                 :             :  *
      36                 :             :  * The item_values input is optional; if omitted, all the items are assumed to
      37                 :             :  * have value 1.
      38                 :             :  *
      39                 :             :  * Returns a Bitmapset of the 0..(n-1) indexes of the items chosen for
      40                 :             :  * inclusion in the solution.
      41                 :             :  *
      42                 :             :  * This uses the usual dynamic-programming algorithm, adapted to reuse the
      43                 :             :  * memory on each pass (by working from larger weights to smaller).  At the
      44                 :             :  * start of pass number i, the values[w] array contains the largest value
      45                 :             :  * computed with total weight <= w, using only items with indices < i; and
      46                 :             :  * sets[w] contains the bitmap of items actually used for that value.  (The
      47                 :             :  * bitmapsets are all pre-initialized with an unused high bit so that memory
      48                 :             :  * allocation is done only once.)
      49                 :             :  */
      50                 :             : Bitmapset *
      51                 :          80 : DiscreteKnapsack(int max_weight, int num_items,
      52                 :             :                                  int *item_weights, double *item_values)
      53                 :             : {
      54                 :          80 :         MemoryContext local_ctx = AllocSetContextCreate(CurrentMemoryContext,
      55                 :             :                                                                                                         "Knapsack",
      56                 :             :                                                                                                         ALLOCSET_SMALL_SIZES);
      57                 :          80 :         MemoryContext oldctx = MemoryContextSwitchTo(local_ctx);
      58                 :          80 :         double     *values;
      59                 :          80 :         Bitmapset **sets;
      60                 :          80 :         Bitmapset  *result;
      61                 :          80 :         int                     i,
      62                 :             :                                 j;
      63                 :             : 
      64         [ +  - ]:          80 :         Assert(max_weight >= 0);
      65         [ +  - ]:          80 :         Assert(num_items > 0 && item_weights);
      66                 :             : 
      67                 :          80 :         values = palloc((1 + max_weight) * sizeof(double));
      68                 :          80 :         sets = palloc((1 + max_weight) * sizeof(Bitmapset *));
      69                 :             : 
      70         [ +  + ]:        4240 :         for (i = 0; i <= max_weight; ++i)
      71                 :             :         {
      72                 :        4160 :                 values[i] = 0;
      73                 :        4160 :                 sets[i] = bms_make_singleton(num_items);
      74                 :        4160 :         }
      75                 :             : 
      76         [ +  + ]:         204 :         for (i = 0; i < num_items; ++i)
      77                 :             :         {
      78                 :         124 :                 int                     iw = item_weights[i];
      79         [ -  + ]:         124 :                 double          iv = item_values ? item_values[i] : 1;
      80                 :             : 
      81         [ +  + ]:        8144 :                 for (j = max_weight; j >= iw; --j)
      82                 :             :                 {
      83                 :        8020 :                         int                     ow = j - iw;
      84                 :             : 
      85         [ -  + ]:        8020 :                         if (values[j] <= values[ow] + iv)
      86                 :             :                         {
      87                 :             :                                 /* copy sets[ow] to sets[j] without realloc */
      88         [ +  + ]:        8020 :                                 if (j != ow)
      89                 :        2247 :                                         sets[j] = bms_replace_members(sets[j], sets[ow]);
      90                 :             : 
      91                 :        8020 :                                 sets[j] = bms_add_member(sets[j], i);
      92                 :             : 
      93                 :        8020 :                                 values[j] = values[ow] + iv;
      94                 :        8020 :                         }
      95                 :        8020 :                 }
      96                 :         124 :         }
      97                 :             : 
      98                 :          80 :         MemoryContextSwitchTo(oldctx);
      99                 :             : 
     100                 :          80 :         result = bms_del_member(bms_copy(sets[max_weight]), num_items);
     101                 :             : 
     102                 :          80 :         MemoryContextDelete(local_ctx);
     103                 :             : 
     104                 :         160 :         return result;
     105                 :          80 : }