#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

Detailed Description

--— KnapsackItem --— 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 320 of file knapsack_solver.h.

Constructor & Destructor Documentation

◆ KnapsackItem()

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

inline

Definition at line 321 of file knapsack_solver.h.

Member Function Documentation

◆ GetEfficiency()

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

inline

Definition at line 323 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 331 of file knapsack_solver.h.

◆ profit

const int64_t operations_research::KnapsackItem::profit

Definition at line 333 of file knapsack_solver.h.

◆ weight

const int64_t operations_research::KnapsackItem::weight

Definition at line 332 of file knapsack_solver.h.

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

ortools/algorithms/knapsack_solver.h

Public Member Functions

Public Attributes