Recursive branch and bound Knapsack solution
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&lt;Knapsack.Item&gt; 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&lt;Knapsack.Item&gt; list, int value, int weight, double bound,
        Cons&lt;Knapsack.Item&gt; taken) {
    if (bound &lt; bestBound) {
        return null;
    }
    if (list == null) {
        bestBound = bound;
        return new Solution(bound, taken);
    }
    Knapsack.Item item = list.head();
    if (item.weight &gt; 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 &gt; left.bound) {
        return right;
    } else {
        return left;
    }
}

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

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

    Knapsack.Item head = list.head();
    if (head.weight &lt;= 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.