operations_research::KnapsackItem Struct Reference

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

#include <knapsack_solver.h>

List of all members.

Public Member Functions
	KnapsackItem (int _id, int64 _weight, int64 _profit)
double	GetEfficiency (int64 profit_max) const
Public Attributes
const int	id
	The 'id' field is used to retrieve the initial item in order to communicate with other propagators and state.
const int64	weight
const int64	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 that 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 212 of file knapsack_solver.h.

---

Constructor & Destructor Documentation

operations_research::KnapsackItem::KnapsackItem	(	int	_id,
		int64	_weight,
		int64	_profit
	)			[inline]

Definition at line 213 of file knapsack_solver.h.

---

Member Function Documentation

double operations_research::KnapsackItem::GetEfficiency

(

int64

profit_max

)

const [inline]

Definition at line 218 of file knapsack_solver.h.

---

Member Data Documentation

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 226 of file knapsack_solver.h.

const int64 operations_research::KnapsackItem::weight

Definition at line 227 of file knapsack_solver.h.

const int64 operations_research::KnapsackItem::profit

Definition at line 228 of file knapsack_solver.h.

---

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

• or-tools/src/algorithms/knapsack_solver.h