Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
example_tdzdd_01knapsack.cpp
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.