example_tdzdd_01knapsack.cpp

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;
}