knapsack

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

• func Get01MaxValue[T any, Weight constraints.Unsigned, Value Number](maxWeight Weight, items []T, getWeight func(*T) Weight, ...) Value
• func Get01Solution[T any, Weight constraints.Unsigned, Value Number](maxWeight Weight, items []T, getWeight func(*T) Weight, ...) (selection []T)
• type Number

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.