branch_and_bound_knapsack_example.cc File Reference

Reference example: 0/1 Knapsack with branch and bound. More...

#include <iostream>
#include <Knapsack.H>
#include <State_Search.H>
#include <tpl_array.H>

Include dependency graph for branch_and_bound_knapsack_example.cc:

Go to the source code of this file.

Functions
int	main ()

Detailed Description

Reference example: 0/1 Knapsack with branch and bound.

Model summary:

• State: partial packing decision, cumulative weight and value.
• Successor generator: take or skip the next item.
• Complete solution: all items have been decided.
• Bound: fractional-knapsack optimistic upper bound.

Build and run:

• cmake --build build --target branch_and_bound_knapsack_example
• ./build/Examples/branch_and_bound_knapsack_example

Definition in file branch_and_bound_knapsack_example.cc.

Function Documentation

main()

int main

(

)

Definition at line 185 of file branch_and_bound_knapsack_example.cc.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::size(), and Aleph::ExplorationPolicy::strategy.