or-tools/src/algorithms/knapsack_solver.cc File Reference

#include "algorithms/knapsack_solver.h"
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
#include "base/concise_iterator.h"
#include "base/stl_util.h"
#include "linear_solver/linear_solver.h"
#include "util/bitset.h"

Go to the source code of this file.

Namespaces
namespace	operations_research
Classes
class	operations_research::KnapsackBruteForceSolver
	KnapsackBruteForceSolver KnapsackBruteForceSolver solves the 0-1 knapsack problem when the number of items is less or equal to 30 with brute force, ie. More...
struct	operations_research::KnapsackItemWithEfficiency
	KnapsackItemWithEfficiency KnapsackItem is a small struct to pair an item weight with its corresponding profit. More...
class	operations_research::Knapsack64ItemsSolver
	Knapsack64ItemsSolver Knapsack64ItemsSolver solves the 0-1 knapsack problem when the number of items is less or equal to 64. More...
class	operations_research::KnapsackDynamicProgrammingSolver
	KnapsackDynamicProgrammingSolver KnapsackDynamicProgrammingSolver solves the 0-1 knapsack problem using dynamic programming. More...
class	operations_research::KnapsackMIPSolver
	KnapsackMIPSolver. More...
Typedefs
typedef std::priority_queue < KnapsackSearchNode *, std::vector < KnapsackSearchNode * > , CompareKnapsackSearchNodePtrInDecreasingUpperBoundOrder >	operations_research::SearchQueue
Functions
bool	operations_research::WillProductOverflow (int64 value_1, int64 value_2)
	Returns true when value_1 * value_2 may overflow int64.
int64	operations_research::UpperBoundOfRatio (int64 numerator_1, int64 numerator_2, int64 denominator)
	Returns an upper bound of (numerator_1 * numerator_2) / denominator.
bool	operations_research::CompareKnapsackItemWithEfficiencyInDecreasingEfficiencyOrder (const KnapsackItemWithEfficiency &item1, const KnapsackItemWithEfficiency &item2)
	Comparator used to sort item in decreasing efficiency order.
Variables
const int	operations_research::kNoSelection = -1
const int	operations_research::kMasterPropagatorId = 0
const int	operations_research::kMaxNumberOfBruteForceItems = 30
const int	operations_research::kMaxNumberOf64Items = 64

---

Variable Documentation

const int64 profit_max

Definition at line 44 of file knapsack_solver.cc.