Algorithms and Data Structures
WORLD SCIENTIFIC eBooks · 2009
your solutions electronically via submit. This is worth 50 % of the coursework for A&DS. In this coursework, we consider the “knapsack counting ” problem. Your mission is to understand, implement, and experiment with a suite of algorithms for this problem. In the knapsack counting problem, we are given as input a list of non-negative integer weights w1, w2,..., wn ∈ N, and an upper bound B ∈ N. We say that some specific set S ⊆ {1,..., n} represents a feasible knapsack solution (wrt w1,..., wn, B) if and only if wi ≤ B. The total number of feasible knapsack solutions (which we wish to count) is count(n, B) =