vrp_knapsack - Experimental

Warning

Possible server crash

  • These functions might create a server crash

Warning

Experimental functions

  • They are not officially of the current release.

  • They likely will not be officially be part of the next release:

    • The functions might not make use of ANY-INTEGER and ANY-NUMERICAL

    • Name might change.

    • Signature might change.

    • Functionality might change.

    • pgTap tests might be missing.

    • Might need c/c++ coding.

    • May lack documentation.

    • Documentation if any might need to be rewritten.

    • Documentation examples might need to be automatically generated.

    • Might need a lot of feedback from the comunity.

    • Might depend on a proposed function of vrpRouting

    • Might depend on a deprecated function of vrpRouting

Availability

Version 0.4.0

Description

The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, Determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible

Signatures

vrp_knapsack(
  Weights_Costs SQL, capacity ANY-INTEGER, [, max_rows])

RETURNS SET OF
(item_id)

Parameters

Parameter

Type

Description

Weights_Costs SQL

TEXT

Weights_Costs SQL query describing the weights and cost of each item

Capacity

ANY-INTEGER

Maximum Capacity of the knapsack.

Optional Parameters

Parameter

Type

Default

Description

max_rows

ANY-INTEGER

\(100000\)

Maximum items(rows) to fetch from knapsack_data table

Inner Queries

Weights_Costs SQL

A SELECT statement that returns the following columns:

id, weight, cost

Column

Type

Default

Description

id

ANY-INTEGER

unique identifier of the item.

weight

ANY-INTEGER

weight of the item.

cost

ANY-INTEGER

cost of the item.

Result Columns

Returns set of

(item_id)

Column

Type

Description

item_id

ANY-INTEGER

Integer to uniquely identify an item in the knapsack

Example

SELECT *
FROM knapsack_query;
 id | weight | cost 
----+--------+------
  1 |     12 |    4
  2 |      2 |    2
  3 |      1 |    1
  4 |      4 |   10
  5 |      1 |    2
(5 rows)

SELECT * 
FROM vrp_knapsack($$SELECT * FROM knapsack_query$$, 15);
 item_id 
---------
       2
       3
       4
       5
(4 rows)