README
¶
go-knapsack: Knapsack Problem Algorithms
This Golang package provides generic algorithms for solving variants of the knapsack problem. It requires Go 1.18 or later.
Use
Run this in your Golang module:
go get github.com/johnmuirjr/go-knapsack
Then import it thus:
import (
"github.com/johnmuirjr/go-knapsack"
)
The package's name is knapsack.
Documentation
¶
Overview ¶
Package knapsack provides algorithms for solving variations of the knapsack problem. See https://en.wikipedia.org/wiki/Knapsack_problem for details.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Get01MaxValue ¶
func Get01MaxValue[T any, Weight constraints.Unsigned, Value Number](maxWeight Weight, items []T, getWeight func(*T) Weight, getValue func(*T) Value) Value
Get01MaxValue solves the 0-1 knapsack problem and returns the maximum value achievable with the specified constraints. maxWeight is the weight capacity of the knapsack. items is the list of items the algorithm can put into the knapsack. getWeight is a callback that returns the weight of a given item. getValue is a callback that returns the value of a given item. Both callbacks MUST be pure functions.
This function runs in O(len(items) * maxWeight) time and uses O(maxWeight) space.
func Get01Solution ¶
func Get01Solution[T any, Weight constraints.Unsigned, Value Number](maxWeight Weight, items []T, getWeight func(*T) Weight, getValue func(*T) Value) (selection []T)
Get01Solution solves the 0-1 knapsack problem and returns a list of items that yields the maximum value given the specified constraints. maxWeight is the weight capacity of the knapsack. items is the list of items the algorithm can put into the knapsack. getWeight is a callback that returns the weight of a given item. getValue is a callback that returns the value of a given item. Both callbacks MUST be pure functions.
This function runs in O(len(items) * maxWeight) time and uses O(len(items) * maxWeight) space.
Types ¶
type Number ¶
type Number interface {
constraints.Integer | constraints.Float
}
Number is a numeric primitive constraint.
Source Files