4
\$\begingroup\$

I've got the imperative styled solution working perfectly. What I'm wondering is how to make a recursive branch and bound.

This is my code below. Evaluate function returns the optimistic estimate, the largest possible value for the set of items which fit into the knapsack (linear relaxation).

For some inputs this outputs an optimal solution, for some it comes really close, for every input it is extremely fast, so it doesn't seem that it hangs anywhere in the search space. So, maybe I'm not branching where I have to or I did something wrong. I'm sure optVal is optimal.

def branch(items: List[Item], taken: List[Item], capacity: Int, eval: Long): (List[Item], Boolean) = items match {
  case x :: xs if x.weight <= capacity => {

    val (bestLeft, opt) = branch(xs, x :: taken, capacity - x.weight, eval)
    if (opt) (bestLeft, opt) // if solution is optimal get out of the tree
    else {
      val evalWithout = evaluate(taken.reverse_:::(xs))

      if (evalWithout < optVal) (bestLeft, opt)
      else branch(xs, taken, capacity, evalWithout)
    }
  }
  case x :: xs => branch(xs, taken, capacity, evaluate(taken.reverse_:::(xs)))

  case Nil => if ((taken map (_.value) sum) == optVal) (taken, true) else (taken, false)
}
\$\endgroup\$

closed as off-topic by 200_success Nov 13 '17 at 8:01

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – 200_success
If this question can be reworded to fit the rules in the help center, please edit the question.

2
\$\begingroup\$

Here is a 'wanna-be functional' solution in java which might help you (it has gone through a set of test cases so I believe it works correctly)

private double bestBound;

public Knapsack.KnapsackResult solve() {
    Cons<Knapsack.Item> list = Cons.from(items);
    bestBound = 0.0;

    double bound = calcBound(list, capacity, 0.0);
    Solution res = dfs(list, 0, capacity, bound, null);

    return buildSolution(res);
}

public Solution dfs(Cons<Knapsack.Item> list, int value, int weight, double bound,
        Cons<Knapsack.Item> taken) {
    if (bound < bestBound) {
        return null;
    }
    if (list == null) {
        bestBound = bound;
        return new Solution(bound, taken);
    }
    Knapsack.Item item = list.head();
    if (item.weight > weight) {
        return notTaking(list, value, weight, taken);
    }

    // taking the item
    Solution left = dfs(list.tail(), value + item.value, weight - item.weight, 
        bound, Cons.cons(item, taken));

    // not taking the item
    Solution right = notTaking(list, value, weight, taken);

    if (left == null) {
        return right;
    }
    if (right == null) {
        return left;
    }
    if (right.bound > left.bound) {
        return right;
    } else {
        return left;
    }
}

private Solution notTaking(Cons<Knapsack.Item> list, int value, int weight, 
        Cons<Knapsack.Item> taken) {
    Cons<Knapsack.Item> tail = list.tail();
    Cons<Knapsack.Item> without;
    if (taken != null) {
        without = taken.reverse().append(tail);
    } else {
        without = tail;
    }
    double newBound = calcBound(without, capacity, 0.0);
    if (newBound <= bestBound) {
        return null;
    }
    return dfs(tail, value, weight, newBound, taken);
}

public static double calcBound(Cons<Knapsack.Item> list, int k, double acc) {
    if (list == null) {
        return acc;
    }

    Knapsack.Item head = list.head();
    if (head.weight <= k) {
        return calcBound(list.tail(), k - head.weight, acc + head.value);
    } else {
        return acc + head.relativeValue() * k;
    }
}

Here I used cons for lists - so it's the same as lists in Scala. There's only one "global" variable - bestBound - which, I know, not very functional, but it was just simpler than passing it around.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the algorithm, the thing is, it's exactly as same as mine. I did eventually discover that for some unknown reason, taken.reverse_:::(xs) is incorrect. By changing it to taken ::: xs the algorithm finds the solution almost instantly for my test cases. \$\endgroup\$ – Looft Aug 7 '13 at 15:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.