It’s easy to generalize 2-sets solution for 3-sets case. In original version, you create array of boolean sums where sums[i] tells whether sum i can be reached with numbers from the set, or not. Then, once array is created, you just see if sums[TOTAL/2] is true or not. Since you said you know old version … Read more
The running time is O(NW) for an unbounded knapsack problem with N items and knapsack of size W. W is not polynomial in the length of the input though, which is what makes it pseudo-polynomial. Consider W = 1,000,000,000,000. It only takes 40 bits to represent this number, so input size = 40, but the … Read more
I believe that you can do this in O(n) time regardless of the choice of by using a modified version of Kadane’s algorithm. To see how this works, let’s consider the case where L = 0. In that case, we want to find the maximum-sum subarray of the original sequence. This can be solved by … Read more
To get all possible sets that elements are equal to ‘a’ or ‘b’ or ‘c’ (our coins) that sum up to ‘X’ you can: Take all such sets that sum up to X-a and add an extra ‘a’ to each one. Take all such sets that sum up to X-b and add an extra ‘b’ … Read more
Be aware that there’s a small mistake in the explanation of the algorithm in the book, look in the errata for the text “(*) Page 297”. About your questions: No, the items don’t need to be sorted, only contiguous (that is, you can’t rearrange them) I believe the easiest way to visualize the algorithm is … Read more
Indeed, there is an approach to this pattern which turns out to work quite often. It can also be used to enumerate all the X with the given property, provided that their number is reasonably small. You can even use it to aggregate some associative operator over all the X with the given property, for … Read more
You could try to use call_user_func_array. But I’ve never tried it on a built-in function before. Here is an example: $dynamicSort = “$sort1,SORT_ASC,$sort2,SORT_ASC,$sort3,SORT_ASC”; $param = array_merge(explode(“,”, $dynamicSort), array($arrayToSort)) call_user_func_array(‘array_multisort’, $param)
Surprisingly, the easily accessible descriptions of this algorithm are not that easy to understand, so the trick is this: As you slide a window of length m over your list of length n, you maintain a deque of all the elements in the current window that might, at some point, become the maximum in any … Read more
Let’s assume that you have a function isWord(w), which checks if w is a word using a dictionary. Let’s for simplicity also assume for now that you only want to know whether for some word w such a splitting is possible. This can be easily done with dynamic programming. Let S[1..length(w)] be a table with … Read more
I found a better way to memoize using Scala: def memoize[I, O](f: I => O): I => O = new mutable.HashMap[I, O]() { override def apply(key: I) = getOrElseUpdate(key, f(key)) } Now you can write fibonacci as follows: lazy val fib: Int => BigInt = memoize { case 0 => 0 case 1 => 1 … Read more