Age         Owner                  TLA  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-2023, 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 "miscadmin.h"
                                 32                 : #include "nodes/bitmapset.h"
                                 33                 : #include "utils/builtins.h"
                                 34                 : #include "utils/memutils.h"
                                 35                 : 
                                 36                 : /*
                                 37                 :  * DiscreteKnapsack
                                 38                 :  *
                                 39                 :  * The item_values input is optional; if omitted, all the items are assumed to
                                 40                 :  * have value 1.
                                 41                 :  *
                                 42                 :  * Returns a Bitmapset of the 0..(n-1) indexes of the items chosen for
                                 43                 :  * inclusion in the solution.
                                 44                 :  *
                                 45                 :  * This uses the usual dynamic-programming algorithm, adapted to reuse the
                                 46                 :  * memory on each pass (by working from larger weights to smaller).  At the
                                 47                 :  * start of pass number i, the values[w] array contains the largest value
                                 48                 :  * computed with total weight <= w, using only items with indices < i; and
                                 49                 :  * sets[w] contains the bitmap of items actually used for that value.  (The
                                 50                 :  * bitmapsets are all pre-initialized with an unused high bit so that memory
                                 51                 :  * allocation is done only once.)
                                 52                 :  */
                                 53                 : Bitmapset *
 2204 rhodiumtoad                54 CBC         198 : DiscreteKnapsack(int max_weight, int num_items,
                                 55                 :                  int *item_weights, double *item_values)
                                 56                 : {
                                 57             198 :     MemoryContext local_ctx = AllocSetContextCreate(CurrentMemoryContext,
                                 58                 :                                                     "Knapsack",
                                 59                 :                                                     ALLOCSET_SMALL_SIZES);
                                 60             198 :     MemoryContext oldctx = MemoryContextSwitchTo(local_ctx);
                                 61                 :     double     *values;
                                 62                 :     Bitmapset **sets;
                                 63                 :     Bitmapset  *result;
                                 64                 :     int         i,
                                 65                 :                 j;
                                 66                 : 
                                 67             198 :     Assert(max_weight >= 0);
                                 68             198 :     Assert(num_items > 0 && item_weights);
                                 69                 : 
                                 70             198 :     values = palloc((1 + max_weight) * sizeof(double));
                                 71             198 :     sets = palloc((1 + max_weight) * sizeof(Bitmapset *));
                                 72                 : 
                                 73           10476 :     for (i = 0; i <= max_weight; ++i)
                                 74                 :     {
                                 75           10278 :         values[i] = 0;
                                 76           10278 :         sets[i] = bms_make_singleton(num_items);
                                 77                 :     }
                                 78                 : 
                                 79             504 :     for (i = 0; i < num_items; ++i)
                                 80                 :     {
                                 81             306 :         int         iw = item_weights[i];
                                 82             306 :         double      iv = item_values ? item_values[i] : 1;
                                 83                 : 
                                 84           18969 :         for (j = max_weight; j >= iw; --j)
                                 85                 :         {
                                 86           18663 :             int         ow = j - iw;
                                 87                 : 
                                 88           18663 :             if (values[j] <= values[ow] + iv)
                                 89                 :             {
                                 90                 :                 /* copy sets[ow] to sets[j] without realloc */
                                 91           18663 :                 if (j != ow)
                                 92                 :                 {
                                 93            6450 :                     sets[j] = bms_del_members(sets[j], sets[j]);
                                 94            6450 :                     sets[j] = bms_add_members(sets[j], sets[ow]);
                                 95                 :                 }
                                 96                 : 
                                 97           18663 :                 sets[j] = bms_add_member(sets[j], i);
                                 98                 : 
                                 99           18663 :                 values[j] = values[ow] + iv;
                                100                 :             }
                                101                 :         }
                                102                 :     }
                                103                 : 
                                104             198 :     MemoryContextSwitchTo(oldctx);
                                105                 : 
                                106             198 :     result = bms_del_member(bms_copy(sets[max_weight]), num_items);
                                107                 : 
                                108             198 :     MemoryContextDelete(local_ctx);
                                109                 : 
                                110             198 :     return result;
                                111                 : }