knapsack

README

knapsack

作者

滕飞 tfcolin@163.com

介绍

用动态规划方法求解任意维整系数约束的背包问题 (knapsack problem)

使用方法

见 manual.pdf

Documentation

Index

• Constants
• func ZeroUtilFunc(x int) float64
• type KnapsackData
  • func InitKnapsackData(reduce_method int, dim int, num_item int) *KnapsackData
  • func (kd *KnapsackData) GetFinalSelect(ii int) int
  • func (kd *KnapsackData) GetFinalValue() float64
  • func (kd *KnapsackData) GetMaxSelectable(ii int) int
  • func (kd *KnapsackData) NextSize(ii int, old_size []int) (new_size []int)
  • func (kd *KnapsackData) SetLimit(limit_coef [][]int, limit []int)
  • func (kd *KnapsackData) SetUtil(ii int, util_func UtilFunction)
  • func (kd *KnapsackData) Solve()
  • func (kd *KnapsackData) SolveStep(ii int)
• type UtilFunction
  • func MakeScalarUtilFunction(c float64) UtilFunction

Constants

const (
	RM_SUM   = 0
	RM_MULTI = 1
	RM_MAX   = 2
	RM_MIN   = 3
)

Functions

func ZeroUtilFunc

func ZeroUtilFunc(x int) float64

Types

type KnapsackData

type KnapsackData struct {
	Dim, Num int
	// contains filtered or unexported fields
}

func InitKnapsackData

func InitKnapsackData(reduce_method int, dim int, num_item int) *KnapsackData

func (*KnapsackData) GetFinalSelect

func (kd *KnapsackData) GetFinalSelect(ii int) int

func (*KnapsackData) GetFinalValue

func (kd *KnapsackData) GetFinalValue() float64

func (*KnapsackData) GetMaxSelectable

func (kd *KnapsackData) GetMaxSelectable(ii int) int

func (*KnapsackData) NextSize

func (kd *KnapsackData) NextSize(ii int, old_size []int) (new_size []int)

func (*KnapsackData) SetLimit

func (kd *KnapsackData) SetLimit(limit_coef [][]int, limit []int)

func (*KnapsackData) SetUtil

func (kd *KnapsackData) SetUtil(ii int, util_func UtilFunction)

func (*KnapsackData) Solve

func (kd *KnapsackData) Solve()

func (*KnapsackData) SolveStep

func (kd *KnapsackData) SolveStep(ii int)

type UtilFunction

type UtilFunction func(x int) float64

func MakeScalarUtilFunction

func MakeScalarUtilFunction(c float64) UtilFunction