Home Manual Reference Source

Function

Static Public Summary
public

Item(weight: *, value: *)

public

Exact DP solution to the 0-1 knapsack problem with integer values given a known upper bound V on OPT.
public

integerValuesKnapsackUnbounded(v: Array, w: Array, n: Number, W: Number, zero: Number | BigInt, V: Number, m: Array): Number

Exact DP solution to the unbounded knapsack problem with integer values given a known upper bound V on OPT.
public

Exact DP solution to the 0-1 knapsack problem with integer weights.
public

Exact DP solution to the unbounded knapsack problem with integer weights.
public

knapsackApprox(eps: Number, v: Array, w: Array, n: Number, W: Number, P: Number): Number

(1-eps)-approx for the knapsack problem.
public

1/2-approximation to the 0-1 knapsack problem.
public

1/2-approximation to the unbounded knapsack problem.

Static Public

public Item(weight: *, value: *) source 

import Item from '@problem-solving/knapsack/src/Item.js'

Params:

NameTypeAttributeDescription
weight *
value *

public integerValuesKnapsack(v: Array, w: Array, n: Number, W: Number, V: Number, m: Array): Number source 

import integerValuesKnapsack from '@problem-solving/knapsack/src/integerValuesKnapsack.js'

Exact DP solution to the 0-1 knapsack problem with integer values given a known upper bound V on OPT. Runs in O(nV) time.

Params:

NameTypeAttributeDescription
v Array

Values.
w Array

Weights.
n Number

Size of the problem.
W Number

Size of the knapsack.
V Number

Any upper bound on OPT >= 0.
m Array

Memory buffer.

Return:

Number

Objective value of the optimum.

public integerValuesKnapsackUnbounded(v: Array, w: Array, n: Number, W: Number, zero: Number | BigInt, V: Number, m: Array): Number source 

import integerValuesKnapsackUnbounded from '@problem-solving/knapsack/src/integerValuesKnapsackUnbounded.js'

Exact DP solution to the unbounded knapsack problem with integer values given a known upper bound V on OPT. Runs in O(nV) time.

Params:

NameTypeAttributeDescription
v Array

Values.
w Array

Weights.
n Number

Size of the problem.
W Number

Size of the knapsack.
zero Number | BigInt

The number 0.
V Number

Any upper bound on OPT >= 0.
m Array

Memory buffer.

Return:

Number

Objective value of the optimum.

public integerWeightsKnapsack(v: Array, w: Array, n: Number, W: Number, m: Array): Number source 

import integerWeightsKnapsack from '@problem-solving/knapsack/src/integerWeightsKnapsack.js'

Exact DP solution to the 0-1 knapsack problem with integer weights. Runs in O(nW) time.

Params:

NameTypeAttributeDescription
v Array

Values.
w Array

Weights.
n Number

Size of the problem.
W Number

Size of the knapsack.
m Array

Memory buffer.

Return:

Number

Objective value of the optimum.

public integerWeightsKnapsackUnbounded(v: Array, w: Array, n: Number, W: Number, m: Array): Number source 

import integerWeightsKnapsackUnbounded from '@problem-solving/knapsack/src/integerWeightsKnapsackUnbounded.js'

Exact DP solution to the unbounded knapsack problem with integer weights. Runs in O(nW) time.

Params:

NameTypeAttributeDescription
v Array

Values.
w Array

Weights.
n Number

Size of the problem.
W Number

Size of the knapsack.
m Array

Memory buffer.

Return:

Number

Objective value of the optimum.

public knapsackApprox(eps: Number, v: Array, w: Array, n: Number, W: Number, P: Number): Number source 

import knapsackApprox from '@problem-solving/knapsack/src/knapsackApprox.js'

(1-eps)-approx for the knapsack problem. Runs in O(N^3/eps) time.

Params:

NameTypeAttributeDescription
eps Number

Approximation constant.
v Array

Values.
w Array

Weights.
n Number

Size of the problem.
W Number

Size of the knapsack.
P Number

Any lower bound on OPT > 0.

Return:

Number

Lower bound on the objective value of a solution, that is at least 1-eps the objective value of the optimum.

public knapsackGreedy(v: Array, w: Array, n: Number, W: Number): Number source 

import knapsackGreedy from '@problem-solving/knapsack/src/knapsackGreedy.js'

1/2-approximation to the 0-1 knapsack problem. Runs in O(n log n) time.

Let OPT' be the value of the LP relaxation. Let v_i be the values of the items ordered by utility. Let k be the largest k such that sum(v[:k]) <= W. Let t = (W-sum(w[:k])) / w_{k+1}, we have t < 1 and OPT' = sum(v[:k]) + t * v_{k+1}. Hence sum(v[:k+1]) > OPT' >= OPT. By partition one of { sum(v[:k]) , v_{k+1} } is at least OPT / 2. Assuming w_i <= W for all i in [N] each of these is feasible.

Params:

NameTypeAttributeDescription
v Array

Values.
w Array

Weights.
n Number

Size of the problem.
W Number

Size of the knapsack.

Return:

Number

Lower bound on the objective value of a solution, that is at least half the objective value of the optimum.

public knapsackUnboundedGreedy(v: Array, w: Array, n: Number, W: Number): Number source 

import knapsackUnboundedGreedy from '@problem-solving/knapsack/src/knapsackUnboundedGreedy.js'

1/2-approximation to the unbounded knapsack problem. Runs in O(n log n) time.

Params:

NameTypeAttributeDescription
v Array

Values.
w Array

Weights.
n Number

Size of the problem.
W Number

Size of the knapsack.

Return:

Number

Lower bound on the objective value of a solution, that is at least half the objective value of the optimum.