PostgreSQL Source Code: src/backend/lib/knapsack.c Source File

PostgreSQL Source Code git master
knapsack.c
Go to the documentation of this file.
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 */
51Bitmapset *
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}
Bitmapset * bms_replace_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:972
Bitmapset * bms_make_singleton(int x)
Definition: bitmapset.c:216
Bitmapset * bms_del_member(Bitmapset *a, int x)
Definition: bitmapset.c:868
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:815
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:122
static Datum values[MAXATTR]
Definition: bootstrap.c:153
Assert(PointerIsAligned(start, uint64))
j
int j
Definition: isn.c:78
i
int i
Definition: isn.c:77
Bitmapset * DiscreteKnapsack(int max_weight, int num_items, int *item_weights, double *item_values)
Definition: knapsack.c:52
void * palloc(Size size)
Definition: mcxt.c:1365
MemoryContext CurrentMemoryContext
Definition: mcxt.c:160
void MemoryContextDelete(MemoryContext context)
Definition: mcxt.c:469
#define AllocSetContextCreate
Definition: memutils.h:129
#define ALLOCSET_SMALL_SIZES
Definition: memutils.h:170
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:124

AltStyle によって変換されたページ (->オリジナル) /