LukasKalbertodt · October 22, 2014 20:33
diff --git a/meta.cpp b/meta.cpp
 /**
 * --- Template Meta Program to solve the Partial Knapsack Problem  ---
 * 
 * This little piece of code solves the partial knapsack problem at compile
 * time. This is not useful in any way. I just wanted to discover the 
 * possibilities of template meta programming.
 * Note that this code is absolutly awful. First of all: It's a "pure" template
 * meta program, which is ugly on it's own. Furthermore my code is ugly in
 * particular. The motivation to clean up super-ugly code to get a little bit
 * less ugly code is... not that high. 
 * 
 * \author Lukas Kalbertodt <[email protected]>
 */
 #include <array>        // Just for output
 #include <cstdint>
 #include <iostream>     // Just for output
 #include <ratio>        // representation of rational numbers
 #include <tuple>        // Just for output
 #include <type_traits>  // useful type traits


 // ############################################################################
 // Basic Helper Stuff
 // ############################################################################

 // compile time struct to hold an ID, a Cost and a Weight
 template <int ID, int C, int W> struct Item {
  static constexpr int cost = C;
  static constexpr int weight = W;
 };

 // is used to store a list of items
 template <typename... Is> struct ItemList {};

 // helper struct to concatenate lists (empty base declaration)
 template <typename, typename> struct Concat;

 // specialization for two item lists
 template <typename... IAs, typename... IBs>
 struct Concat<ItemList<IAs...>, ItemList<IBs...>> {
  using type = ItemList<IAs..., IBs...>;
 };

 // ------------------- RemoveElement -------------------------------------------
 // helper struct to remove one element Needle of a list Os 
 // (empty base declaration)
 template <typename Needle, typename... Os> struct RemoveElement;

 // specialization for empty list -> result is empty list
 template <typename Needle> struct RemoveElement<Needle> {
  using type = ItemList<>;
 };

 // specialization for a list in which the first element differs from the Needle
 // -> result is Concat<Head, RemoveElement<Needle, Tail>
 template <typename Needle, typename Head, typename... Tail>
 struct RemoveElement<Needle, Head, Tail...> {
  using type
    = typename Concat<ItemList<Head>,
                      typename RemoveElement<Needle,
                                            Tail...>::type>::type;
 };

 // specialization for a list in which the first element equals the Needle
 // -> result is RemoveElement<Needle, Tail>
 template <typename Needle, typename... Tail>
 struct RemoveElement<Needle, Needle, Tail...> {
  using type = typename RemoveElement<Needle,
                                      Tail...>::type;
 };



 // ############################################################################
 // Sorting
 // ############################################################################

 // ------------------- MaxItemBelow -------------------------------------------
 // returns the item with the maximal Cost/Weight ratio that is less than the 
 // std::ratio given as first parameter (Cut).
 // Note: I don't actually use the "Below"-Feature of this anymore. This whole
 // program should still run without that, but I'm to lazy to remove it ;)
 template <typename Cut, typename... Ts> struct MaxItemBelow;

 // specialization for just one item -> maximum is this item of course 
 template <std::intmax_t Num, std::intmax_t Den, typename I>
 struct MaxItemBelow<std::ratio<Num, Den>, I> {
  using max = I;
 };

 // specialization for a list with at least two items ->
 // It removes one element (from those two) and "calls" itself in a recursive way
 // with a list which size is decreased by one. To decide which item is dropped 
 // it evaluates this expression: 
 // valid(i0) && (i0 > i1 || !valid(i1)) , where
 // valid() checks if the value of the item is below the Cut.
 // In other words: With each recursive "call" it removes one elment from the 
 // list that is not the maximum below the Cut, until just one item is left
 template <std::intmax_t Num, std::intmax_t Den,
          int ID0, int C0, int W0,
          int ID1, int C1, int W1,
          int... IDs, int... Cs, int... Ws>
 struct MaxItemBelow<std::ratio<Num, Den>,
                    Item<ID0, C0, W0>,
                    Item<ID1, C1, W1>,
                    Item<IDs, Cs, Ws>...>
  : MaxItemBelow<std::ratio<Num, Den>,
                 typename std::
                   conditional<std::ratio_less<std::ratio<C0, W0>,
                                               std::ratio<Num, Den>>::value && (
                                   std::ratio_greater<std::ratio<C0, W0>,
                                                      std::ratio<C1, W1>>::value
                                   || !std::ratio_less<std::ratio<C1, W1>,
                                                       std::ratio<Num,
                                                                  Den>>::value),
                               Item<ID0, C0, W0>,
                               Item<ID1, C1, W1>>::type,
                 Item<IDs, Cs, Ws>...> {};



 // ------------------- SortHelper  --------------------------------------------
 // sorts all items in the given list whose value is below Max
 template <typename Max, typename List> struct SortHelper;

 // specialization for one item in the list -> the list is already sorted
 template <typename Max, typename I>
 struct SortHelper<Max, ItemList<I>> {
  using type = ItemList<I>;
 };

 // specialization for a list containing more than one item ->
 // max is the maximal item below Max
 // newlist is the given list without 'max'
 // type is a list of items containing all items in the input list with 'max'
 // at the beginning
 template <typename Max, typename I0, typename... Is>
 struct SortHelper<Max, ItemList<I0, Is...>> {
 private:
  using max = typename MaxItemBelow<Max, I0, Is...>::max;
  using newlist = typename RemoveElement<max, I0, Is...>::type;

 public:
  using type
    = typename Concat<ItemList<max>,
                      typename SortHelper<std::ratio<max::cost, max::weight>,
                                          newlist>::type>::type;
 };




 // ------------------- PackHelper  --------------------------------------------
 // Gets a sorted list of items and creates a list of 
 // {ItemID, num, den} where num/den is how much of the ItemID is used in the
 // result. WL = weight left
 template <int WL, bool OverZero, typename... Is>
 struct PackHelper;

 // specialization for a list with at least one element and a knapsack with
 // space left ->
 // We calculate how much of that item fits into the knapsack: If the item weight
 // is less than the available weight in the knapsack, we can fit everything of
 // the item (1). Else we fit as much as we can, which is 
 // (left_available_weight/item_weight).
 // After calculating the share of the current item we recurse.
 template <int WL, int ID0, int C0, int W0, int... IDs, int... Cs, int... Ws>
 struct PackHelper<WL, true, ItemList<Item<ID0, C0, W0>, Item<IDs, Cs, Ws>...>> {
 private:
  using head = Item<ID0, 
                        (W0 < WL) ? 1 : std::ratio<WL, W0>::num,
                        (W0 < WL) ? 1 : std::ratio<WL, W0>::den>;
  using tail = typename PackHelper<WL - W0,
                                   ((WL - W0) > 0),
                                   ItemList<Item<IDs, Cs, Ws>...>>::type;

 public:
  using type = typename Concat<ItemList<head>, tail>::type;
 };

 // specialization for a full knapsack with still items left ->
 // We can't fit any more items into the knapsack
 template <int WL, typename... Is>
 struct PackHelper<WL, false, ItemList<Is...>> {
  using type = ItemList<>;
 };

 // specialization for an empty list and a knapsack which is not full ->
 // We don't have to process any more items (easy problem instance)
 template <int WL>
 struct PackHelper<WL, true, ItemList<>> {
  using type = ItemList<>;
 };


 // ############################################################################
 // knapsack
 // ############################################################################
 // Main "public" "function": Instance of the partial knapsack problem as 
 // template parameter: Max is the the size of the knapsack followed by a list
 // of items
 template <int Max, typename... Is>
 struct Knapsack {
 private:
  // sorts the list of items
  using sorted = typename SortHelper<std::ratio<0, 1>, ItemList<Is...>>::type;

 public:
  // the resulting item list where (cost/weight) is the share of the item ID
  using Result = typename PackHelper<Max, (Max > 0), sorted>::type;
 };


 // ############################################################################
 // OutHelper
 // ############################################################################
 // Just some helper structs to create an array of the compile time template list
 // to print it on the screen... Similar to STL's implementation in his variadic
 // sorter:
 // https://onedrive.live.com/?cid=e66e02dc83efb165&id=E66E02DC83EFB165%21306
 template <typename Is>
 struct OutHelper;

 template <int... IDs, int... Cs, int... Ws>
 struct OutHelper<ItemList<Item<IDs,Cs, Ws>...>> {
  static const std::array<std::tuple<int, int, int>, sizeof...(IDs)> arr;
 };

 template <int... IDs, int... Cs, int... Ws>
 const std::array<std::tuple<int, int, int>, sizeof...(IDs)>
  OutHelper<ItemList<Item<IDs, Cs, Ws>...>>::arr
  = {{std::make_tuple(IDs, Cs, Ws)...}};




 int main() {
  using namespace std;

  // "call" the solver with a knapsack instance          
  //                                      ID | C | W        C/W
  using res = OutHelper<Knapsack<200, Item<0, 20, 100>,  // 0,2
                                      Item<1, 15, 80>,   // 0,1875
                                      Item<2, 15, 40>,   // 0,375
                                      Item<3, 10, 20>    // 0,5
                                      >::Result>;

  // print result                                 
  for (auto& e : res::arr) {
    cout << "ID " << get<0>(e) << ":\t" << static_cast<float>(get<1>(e)) / get<2>(e) << endl;
  }
  cout << endl;
 }
	/**
	* --- Template Meta Program to solve the Partial Knapsack Problem ---
	*
	* This little piece of code solves the partial knapsack problem at compile
	* time. This is not useful in any way. I just wanted to discover the
	* possibilities of template meta programming.
	* Note that this code is absolutly awful. First of all: It's a "pure" template
	* meta program, which is ugly on it's own. Furthermore my code is ugly in
	* particular. The motivation to clean up super-ugly code to get a little bit
	* less ugly code is... not that high.
	*
	* \author Lukas Kalbertodt <[email protected]>
	*/
	#include <array> // Just for output
	#include <cstdint>
	#include <iostream> // Just for output
	#include <ratio> // representation of rational numbers
	#include <tuple> // Just for output
	#include <type_traits> // useful type traits


	// ############################################################################
	// Basic Helper Stuff
	// ############################################################################

	// compile time struct to hold an ID, a Cost and a Weight
	template <int ID, int C, int W> struct Item {
	static constexpr int cost = C;
	static constexpr int weight = W;
	};

	// is used to store a list of items
	template <typename... Is> struct ItemList {};

	// helper struct to concatenate lists (empty base declaration)
	template <typename, typename> struct Concat;

	// specialization for two item lists
	template <typename... IAs, typename... IBs>
	struct Concat<ItemList<IAs...>, ItemList<IBs...>> {
	using type = ItemList<IAs..., IBs...>;
	};

	// ------------------- RemoveElement -------------------------------------------
	// helper struct to remove one element Needle of a list Os
	// (empty base declaration)
	template <typename Needle, typename... Os> struct RemoveElement;

	// specialization for empty list -> result is empty list
	template <typename Needle> struct RemoveElement<Needle> {
	using type = ItemList<>;
	};

	// specialization for a list in which the first element differs from the Needle
	// -> result is Concat<Head, RemoveElement<Needle, Tail>
	template <typename Needle, typename Head, typename... Tail>
	struct RemoveElement<Needle, Head, Tail...> {
	using type
	= typename Concat<ItemList<Head>,
	typename RemoveElement<Needle,
	Tail...>::type>::type;
	};

	// specialization for a list in which the first element equals the Needle
	// -> result is RemoveElement<Needle, Tail>
	template <typename Needle, typename... Tail>
	struct RemoveElement<Needle, Needle, Tail...> {
	using type = typename RemoveElement<Needle,
	Tail...>::type;
	};



	// ############################################################################
	// Sorting
	// ############################################################################

	// ------------------- MaxItemBelow -------------------------------------------
	// returns the item with the maximal Cost/Weight ratio that is less than the
	// std::ratio given as first parameter (Cut).
	// Note: I don't actually use the "Below"-Feature of this anymore. This whole
	// program should still run without that, but I'm to lazy to remove it ;)
	template <typename Cut, typename... Ts> struct MaxItemBelow;

	// specialization for just one item -> maximum is this item of course
	template <std::intmax_t Num, std::intmax_t Den, typename I>
	struct MaxItemBelow<std::ratio<Num, Den>, I> {
	using max = I;
	};

	// specialization for a list with at least two items ->
	// It removes one element (from those two) and "calls" itself in a recursive way
	// with a list which size is decreased by one. To decide which item is dropped
	// it evaluates this expression:
	// valid(i0) && (i0 > i1 \|\| !valid(i1)) , where
	// valid() checks if the value of the item is below the Cut.
	// In other words: With each recursive "call" it removes one elment from the
	// list that is not the maximum below the Cut, until just one item is left
	template <std::intmax_t Num, std::intmax_t Den,
	int ID0, int C0, int W0,
	int ID1, int C1, int W1,
	int... IDs, int... Cs, int... Ws>
	struct MaxItemBelow<std::ratio<Num, Den>,
	Item<ID0, C0, W0>,
	Item<ID1, C1, W1>,
	Item<IDs, Cs, Ws>...>
	: MaxItemBelow<std::ratio<Num, Den>,
	typename std::
	conditional<std::ratio_less<std::ratio<C0, W0>,
	std::ratio<Num, Den>>::value && (
	std::ratio_greater<std::ratio<C0, W0>,
	std::ratio<C1, W1>>::value
	\|\| !std::ratio_less<std::ratio<C1, W1>,
	std::ratio<Num,
	Den>>::value),
	Item<ID0, C0, W0>,
	Item<ID1, C1, W1>>::type,
	Item<IDs, Cs, Ws>...> {};



	// ------------------- SortHelper --------------------------------------------
	// sorts all items in the given list whose value is below Max
	template <typename Max, typename List> struct SortHelper;

	// specialization for one item in the list -> the list is already sorted
	template <typename Max, typename I>
	struct SortHelper<Max, ItemList<I>> {
	using type = ItemList<I>;
	};

	// specialization for a list containing more than one item ->
	// max is the maximal item below Max
	// newlist is the given list without 'max'
	// type is a list of items containing all items in the input list with 'max'
	// at the beginning
	template <typename Max, typename I0, typename... Is>
	struct SortHelper<Max, ItemList<I0, Is...>> {
	private:
	using max = typename MaxItemBelow<Max, I0, Is...>::max;
	using newlist = typename RemoveElement<max, I0, Is...>::type;

	public:
	using type
	= typename Concat<ItemList<max>,
	typename SortHelper<std::ratio<max::cost, max::weight>,
	newlist>::type>::type;
	};




	// ------------------- PackHelper --------------------------------------------
	// Gets a sorted list of items and creates a list of
	// {ItemID, num, den} where num/den is how much of the ItemID is used in the
	// result. WL = weight left
	template <int WL, bool OverZero, typename... Is>
	struct PackHelper;

	// specialization for a list with at least one element and a knapsack with
	// space left ->
	// We calculate how much of that item fits into the knapsack: If the item weight
	// is less than the available weight in the knapsack, we can fit everything of
	// the item (1). Else we fit as much as we can, which is
	// (left_available_weight/item_weight).
	// After calculating the share of the current item we recurse.
	template <int WL, int ID0, int C0, int W0, int... IDs, int... Cs, int... Ws>
	struct PackHelper<WL, true, ItemList<Item<ID0, C0, W0>, Item<IDs, Cs, Ws>...>> {
	private:
	using head = Item<ID0,
	(W0 < WL) ? 1 : std::ratio<WL, W0>::num,
	(W0 < WL) ? 1 : std::ratio<WL, W0>::den>;
	using tail = typename PackHelper<WL - W0,
	((WL - W0) > 0),
	ItemList<Item<IDs, Cs, Ws>...>>::type;

	public:
	using type = typename Concat<ItemList<head>, tail>::type;
	};

	// specialization for a full knapsack with still items left ->
	// We can't fit any more items into the knapsack
	template <int WL, typename... Is>
	struct PackHelper<WL, false, ItemList<Is...>> {
	using type = ItemList<>;
	};

	// specialization for an empty list and a knapsack which is not full ->
	// We don't have to process any more items (easy problem instance)
	template <int WL>
	struct PackHelper<WL, true, ItemList<>> {
	using type = ItemList<>;
	};


	// ############################################################################
	// knapsack
	// ############################################################################
	// Main "public" "function": Instance of the partial knapsack problem as
	// template parameter: Max is the the size of the knapsack followed by a list
	// of items
	template <int Max, typename... Is>
	struct Knapsack {
	private:
	// sorts the list of items
	using sorted = typename SortHelper<std::ratio<0, 1>, ItemList<Is...>>::type;

	public:
	// the resulting item list where (cost/weight) is the share of the item ID
	using Result = typename PackHelper<Max, (Max > 0), sorted>::type;
	};


	// ############################################################################
	// OutHelper
	// ############################################################################
	// Just some helper structs to create an array of the compile time template list
	// to print it on the screen... Similar to STL's implementation in his variadic
	// sorter:
	// https://onedrive.live.com/?cid=e66e02dc83efb165&id=E66E02DC83EFB165%21306
	template <typename Is>
	struct OutHelper;

	template <int... IDs, int... Cs, int... Ws>
	struct OutHelper<ItemList<Item<IDs,Cs, Ws>...>> {
	static const std::array<std::tuple<int, int, int>, sizeof...(IDs)> arr;
	};

	template <int... IDs, int... Cs, int... Ws>
	const std::array<std::tuple<int, int, int>, sizeof...(IDs)>
	OutHelper<ItemList<Item<IDs, Cs, Ws>...>>::arr
	= {{std::make_tuple(IDs, Cs, Ws)...}};




	int main() {
	using namespace std;

	// "call" the solver with a knapsack instance
	// ID \| C \| W C/W
	using res = OutHelper<Knapsack<200, Item<0, 20, 100>, // 0,2
	Item<1, 15, 80>, // 0,1875
	Item<2, 15, 40>, // 0,375
	Item<3, 10, 20> // 0,5
	>::Result>;

	// print result
	for (auto& e : res::arr) {
	cout << "ID " << get<0>(e) << ":\t" << static_cast<float>(get<1>(e)) / get<2>(e) << endl;
	}
	cout << endl;
	}