What is the C plus plus Algorithm for Knapsack Problem?

Answer 1

#include<iostream>

#include<vector>

#include<cassert>

template<typename _Ty>

class subset

{

public:

using value_type = typename _Ty::const_iterator;

using container_type = std::vector<value_type>;

using iterator = typename container_type::iterator;

using const_iterator = typename container_type::const_iterator;

using reverse_iterator = typename container_type::reverse_iterator;

using const_reverse_iterator = typename container_type::const_reverse_iterator;

using size_type = typename container_type::size_type;

~subset (void) {};

explicit subset (const _Ty&);

subset (const subset&) = delete;

subset (subset&&) = delete;

subset& operator= (const subset&) = delete;

subset& operator= (subset&&) = delete;

const container_type& first (size_type);

const container_type& next (void);

private:

size_type m_size; // desired size of the subset

container_type m_set; // iterators to the full set

container_type m_subset; // subset of the full set of iterators

const_iterator find (const value_type&) const;

const bool get_next (const bool = true);

};

template<typename _Ty>

inline subset<_Ty>::subset (const _Ty& set):

m_size {set.size()}, m_set {}, m_subset {}

{

for (value_type it=set.begin(); it!=set.end(); ++it)

m_set.push_back (it);

m_set.shrink_to_fit();

}

template<typename _Ty>

inline typename subset<_Ty>::const_iterator subset<_Ty>::find (

const value_type& value) const

{

const_iterator it=m_set.begin();

while (it!=m_set.end() && *it!=value) ++it;

return it;

}

template<typename _Ty>

inline const typename subset<_Ty>::container_type& subset<_Ty>::first (

size_type count)

{

assert (count <= m_set.size());

m_size = count;

m_subset.clear();

for (const_iterator it=m_set.begin(); count--; ++it)

m_subset.push_back (*it);

return m_subset;

}

template<typename _Ty>

inline const bool subset<_Ty>::get_next (

const bool pop /* = true */)

{

const_reverse_iterator sub_it = m_subset.rbegin();

const_iterator set_it = find (*sub_it);

if (pop)

m_subset.pop_back();

if (++set_it != m_set.end())

m_subset.push_back (*set_it);

return m_subset.size() 1U)

return m_subset;

const value_type value = m_set.back();

m_set.pop_back();

--m_size;

next();

m_set.push_back (value);

if (m_size++ != m_subset.size())

return m_subset;

get_next (false);

return m_subset;

}

struct item

{

size_t value {0};

size_t weight {0};

item (size_t v=0, size_t w=0): value{v}, weight{w} {}

};

using vector = std::vector<item>;

item sum (vector& v)

{

item result;

for( auto i : v)

{

result.weight += i.weight;

result.value += i.value;

}

return result;

}

vector knapsack (vector items, size_t capacity)

{

vector v;

subset<vector> set {items};

for (size_t n=items.size(); n; --n)

{

subset<vector>::container_type selection {set.first (n)};

for (; selection.size(); selection=set.next())

{

vector t;

for (auto i : selection)

{

t.push_back (*i);

}

item s = sum (t);

if (s.weight <= capacity && sum(v).value < s.value)

v = t;

}

}

return v;

}

int main()

{

size_t capacity {4};

vector items {{1,8},{2,4},{3,1},{2,5},{2,3}};

vector rucksack = knapsack (items, capacity);

std::cout << "Items:\n" << std::endl;

for (auto i : items)

std::cout << '£' << i.value << '\t' << i.weight << "kg" << std::endl;

std::cout << std::endl;

std::cout << "Optimal selection for capacity " << capacity << "kg\n" << std::endl;

for (auto r : rucksack)

std::cout << '£' << r.value << '\t' << r.weight << "kg" << std::endl;

std::cout << std::endl;

item s = sum (rucksack);

std::cout << "Total value and weight:\n" << std::endl;

std::cout << '£' << s.value << '\t' << s.weight << "kg" << std::endl;

std::cout << std::endl;

}