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-2024, PostgreSQL Global Development Group
      19             :  *
      20             :  * IDENTIFICATION
      21             :  *    src/backend/lib/knapsack.c
      22             :  *
      23             :  *-------------------------------------------------------------------------
      24             :  */
      25             : #include "postgres.h"
      26             : 
      27             : #include <math.h>
      28             : #include <limits.h>
      29             : 
      30             : #include "lib/knapsack.h"
      31             : #include "nodes/bitmapset.h"
      32             : #include "utils/memutils.h"
      33             : 
      34             : /*
      35             :  * DiscreteKnapsack
      36             :  *
      37             :  * The item_values input is optional; if omitted, all the items are assumed to
      38             :  * have value 1.
      39             :  *
      40             :  * Returns a Bitmapset of the 0..(n-1) indexes of the items chosen for
      41             :  * inclusion in the solution.
      42             :  *
      43             :  * This uses the usual dynamic-programming algorithm, adapted to reuse the
      44             :  * memory on each pass (by working from larger weights to smaller).  At the
      45             :  * start of pass number i, the values[w] array contains the largest value
      46             :  * computed with total weight <= w, using only items with indices < i; and
      47             :  * sets[w] contains the bitmap of items actually used for that value.  (The
      48             :  * bitmapsets are all pre-initialized with an unused high bit so that memory
      49             :  * allocation is done only once.)
      50             :  */
      51             : Bitmapset *
      52         420 : DiscreteKnapsack(int max_weight, int num_items,
      53             :                  int *item_weights, double *item_values)
      54             : {
      55         420 :     MemoryContext local_ctx = AllocSetContextCreate(CurrentMemoryContext,
      56             :                                                     "Knapsack",
      57             :                                                     ALLOCSET_SMALL_SIZES);
      58         420 :     MemoryContext oldctx = MemoryContextSwitchTo(local_ctx);
      59             :     double     *values;
      60             :     Bitmapset **sets;
      61             :     Bitmapset  *result;
      62             :     int         i,
      63             :                 j;
      64             : 
      65             :     Assert(max_weight >= 0);
      66             :     Assert(num_items > 0 && item_weights);
      67             : 
      68         420 :     values = palloc((1 + max_weight) * sizeof(double));
      69         420 :     sets = palloc((1 + max_weight) * sizeof(Bitmapset *));
      70             : 
      71       21960 :     for (i = 0; i <= max_weight; ++i)
      72             :     {
      73       21540 :         values[i] = 0;
      74       21540 :         sets[i] = bms_make_singleton(num_items);
      75             :     }
      76             : 
      77        1056 :     for (i = 0; i < num_items; ++i)
      78             :     {
      79         636 :         int         iw = item_weights[i];
      80         636 :         double      iv = item_values ? item_values[i] : 1;
      81             : 
      82       38946 :         for (j = max_weight; j >= iw; --j)
      83             :         {
      84       38310 :             int         ow = j - iw;
      85             : 
      86       38310 :             if (values[j] <= values[ow] + iv)
      87             :             {
      88             :                 /* copy sets[ow] to sets[j] without realloc */
      89       38310 :                 if (j != ow)
      90       12900 :                     sets[j] = bms_replace_members(sets[j], sets[ow]);
      91             : 
      92       38310 :                 sets[j] = bms_add_member(sets[j], i);
      93             : 
      94       38310 :                 values[j] = values[ow] + iv;
      95             :             }
      96             :         }
      97             :     }
      98             : 
      99         420 :     MemoryContextSwitchTo(oldctx);
     100             : 
     101         420 :     result = bms_del_member(bms_copy(sets[max_weight]), num_items);
     102             : 
     103         420 :     MemoryContextDelete(local_ctx);
     104             : 
     105         420 :     return result;
     106             : }