Knapsack.H File Reference

Classical knapsack problem variants (0/1, unbounded, bounded). More...

#include <algorithm>
#include <concepts>
#include <cstddef>
#include <limits>
#include <type_traits>
#include <utility>
#include <ah-errors.H>
#include <tpl_array.H>

Include dependency graph for Knapsack.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::Knapsack_Item< W, V >
	An item for knapsack problems. More...
struct	Aleph::Knapsack_Result< V >
	Result of a knapsack computation. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::knapsack_detail

Functions
template<std::integral W>
size_t	Aleph::knapsack_detail::to_size_checked (const W value, const char *fn_name, const char *field_name)
template<std::integral W, typename V >
Array< size_t >	Aleph::knapsack_detail::extract_weights_checked (const Array< Knapsack_Item< W, V > > &items, const char *fn_name)
template<typename V >
V	Aleph::knapsack_detail::dp_add (V a, V b) noexcept
template<typename V , std::integral W>
Knapsack_Result< V >	Aleph::knapsack_01 (const Array< Knapsack_Item< W, V > > &items, W capacity)
	Solve the 0/1 Knapsack problem with item reconstruction.
template<typename V , std::integral W>
V	Aleph::knapsack_01_value (const Array< Knapsack_Item< W, V > > &items, W capacity)
	Solve the 0/1 Knapsack problem (value only, space-optimized).
template<typename V , std::integral W>
Knapsack_Result< V >	Aleph::knapsack_unbounded (const Array< Knapsack_Item< W, V > > &items, W capacity)
	Solve the Unbounded Knapsack problem with reconstruction.
template<typename V , std::integral W>
Knapsack_Result< V >	Aleph::knapsack_bounded (const Array< Knapsack_Item< W, V > > &items, const Array< size_t > &counts, W capacity)
	Solve the Bounded Knapsack problem with reconstruction.

Detailed Description

Classical knapsack problem variants (0/1, unbounded, bounded).

The knapsack problem is a fundamental combinatorial optimization problem: given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

This header provides high-performance dynamic programming solutions for:

• 0/1 Knapsack: Each item can be used at most once.
• Unbounded Knapsack: Unlimited copies of each item are available.
• Bounded Knapsack: A limited number of copies of each item is available.

Complexity

Variant	Time	Space
0/1 Knapsack	O(n * capacity)	O(capacity)
Unbounded	O(n * capacity)	O(capacity)
Bounded	O(capacity * sum(log c_i))	O(capacity)

Example

Array<Knapsack_Item<size_t, int>> items = {
  {2, 40}, {3, 50}, {4, 70}, {5, 80}
};
size_t capacity = 8;
 
// Solve 0/1 Knapsack
auto res = knapsack_01(items, capacity);
// res.optimal_value = 130 (items {3, 50} and {5, 80})
// res.selected_items contains the indices {1, 3}

Definition in file Knapsack.H.