Detailed Description

KnapsackItem is a small struct to pair an item weight with its corresponding profit.

The aim of the knapsack problem is to pack as many valuable items as possible. A straight forward heuristic is to take those with the greatest profit-per-unit-weight. This ratio is called efficiency in this implementation. So items will be grouped in vectors, and sorted by decreasing efficiency.

Note: profits are duplicated for each dimension. This is done to simplify the code, especially the GetEfficiency method and vector sorting. As there usually are only few dimensions, the overhead should not be an issue.

Definition at line 293 of file knapsack_solver.h.

#include <knapsack_solver.h>

Public Member Functions
	KnapsackItem (int _id, int64_t _weight, int64_t _profit)
double	GetEfficiency (int64_t profit_max) const

Public Attributes
const int	id
const int64_t	weight
const int64_t	profit

Constructor & Destructor Documentation

◆ KnapsackItem()

operations_research::KnapsackItem::KnapsackItem	(	int	_id,
		int64_t	_weight,
		int64_t	_profit )

inline

Definition at line 294 of file knapsack_solver.h.

Member Function Documentation

◆ GetEfficiency()

double operations_research::KnapsackItem::GetEfficiency ( int64_t profit_max ) const

inline

Definition at line 296 of file knapsack_solver.h.

Member Data Documentation

◆ id

const int operations_research::KnapsackItem::id

The 'id' field is used to retrieve the initial item in order to communicate with other propagators and state.

Definition at line 304 of file knapsack_solver.h.

◆ profit

const int64_t operations_research::KnapsackItem::profit

Definition at line 306 of file knapsack_solver.h.

◆ weight

const int64_t operations_research::KnapsackItem::weight

Definition at line 305 of file knapsack_solver.h.

The documentation for this struct was generated from the following file:

ortools/algorithms/knapsack_solver.h