Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <iostream>
- #include <tdzdd/DdSpec.hpp>
- #include <tdzdd/DdStructure.hpp>
- using namespace std;
- class KnapsackZdd : public tdzdd::DdSpec<KnapsackZdd, int, 2> {
- int const n;
- int const *w;
- int const W;
- public:
- KnapsackZdd (int n, int *w, int W) : n(n), w(w), W(W) { }
- int getRoot(int& state) {
- state = 0;
- return n;
- }
- int getChild(int& state, int level, int value) const {
- if (value == 1)
- state += w[n - level];
- level--;
- if (state > W)
- return 0;
- if (level == 0)
- return -1;
- return level;
- }
- };
- class MaxElement : public tdzdd::DdEval<MaxElement,int> {
- int const n;
- int const *c;
- public:
- MaxElement(int n, int *c) : n(n), c(c) { }
- void evalTerminal(int& val, bool one) const {
- val = one ? 0 : INT_MIN;
- }
- void evalNode(int& val, int level, tdzdd::DdValues<int,2> const& values) const {
- val= std::max(values.get(0), values.get(1) + c[n - level]);
- }
- };
- int main() {
- const int n = 5, W = 10;
- int w[] = {4, 4, 10, 3, 5};
- int c[] = {5, 8, 3, 4, 6};
- KnapsackZdd knapsack(n, w, W);
- tdzdd::DdStructure<2> dd(knapsack);
- ofstream output("knapsack.dot");
- dd.dumpDot(output);
- // evaluate max answer
- cout << "max val = " << dd.evaluate(MaxElement(n, c)) << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement