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