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          411 : DiscreteKnapsack(int max_weight, int num_items,
      52              :                  int *item_weights, double *item_values)
      53              : {
      54          411 :     MemoryContext local_ctx = AllocSetContextCreate(CurrentMemoryContext,
      55              :                                                     "Knapsack",
      56              :                                                     ALLOCSET_SMALL_SIZES);
      57          411 :     MemoryContext oldctx = MemoryContextSwitchTo(local_ctx);
      58              :     double     *values;
      59              :     Bitmapset **sets;
      60              :     Bitmapset  *result;
      61              :     int         i,
      62              :                 j;
      63              : 
      64              :     Assert(max_weight >= 0);
      65              :     Assert(num_items > 0 && item_weights);
      66              : 
      67          411 :     values = palloc((1 + max_weight) * sizeof(double));
      68          411 :     sets = palloc((1 + max_weight) * sizeof(Bitmapset *));
      69              : 
      70        21662 :     for (i = 0; i <= max_weight; ++i)
      71              :     {
      72        21251 :         values[i] = 0;
      73        21251 :         sets[i] = bms_make_singleton(num_items);
      74              :     }
      75              : 
      76         1042 :     for (i = 0; i < num_items; ++i)
      77              :     {
      78          631 :         int         iw = item_weights[i];
      79          631 :         double      iv = item_values ? item_values[i] : 1;
      80              : 
      81        41182 :         for (j = max_weight; j >= iw; --j)
      82              :         {
      83        40551 :             int         ow = j - iw;
      84              : 
      85        40551 :             if (values[j] <= values[ow] + iv)
      86              :             {
      87              :                 /* copy sets[ow] to sets[j] without realloc */
      88        40551 :                 if (j != ow)
      89        11235 :                     sets[j] = bms_replace_members(sets[j], sets[ow]);
      90              : 
      91        40551 :                 sets[j] = bms_add_member(sets[j], i);
      92              : 
      93        40551 :                 values[j] = values[ow] + iv;
      94              :             }
      95              :         }
      96              :     }
      97              : 
      98          411 :     MemoryContextSwitchTo(oldctx);
      99              : 
     100          411 :     result = bms_del_member(bms_copy(sets[max_weight]), num_items);
     101              : 
     102          411 :     MemoryContextDelete(local_ctx);
     103              : 
     104          411 :     return result;
     105              : }