Rincer
BAN USERVariation of the knapsack problem?
Convert the character string and all the words in the dictionary to int a[26] where a[i] = the number of times a certain character appears in the set/ dictionary words. The converted set is your 'knapsack';
Base cases are if all elements of a[26] are 0, set is empty return true, otherwise if then word index is -1 return false (tried all the words and there are still letters left).
if not a base case then in a loop try to choose the current word 0..m times and recursively solve for the word current-1 with the remainder of the set/knapsack. If any of the solutions return true then return true. otherwise if you can't choose the current word anymore because the set doesnt have enough letters but is not empty return false.
Variation of the knapsack problem?
Convert the character string and all the words in the dictionary to int a[26] where a[i] = the number of times a certain character appears in the set/ dictionary words. The converted set is your 'knapsack';
Difference here is that you can choose each word multiple times. So the knapsack algorithm needs to be extended to use a 3d array instead of 2d one to cache the sub problem results. And at each step you try to choose the word 0 .. n times until it doesn't fit in the 'knapsack' anymore then recursively solve for the next word and the remainder of the set?
For each vertex traverse all its edges in pairs. For each edge pair see if the vertices are connected, if so its a triangle. Since the same triangle will be reported 3 times (for each vertex), divide the result by 3. This algorithm is O(n) complexity.
For example above:
0 1
2 1
0 2
4 1
Vertex 0 edge pair (0,1) and (0,2) , select any of the 2 connected vertices and see if there is an edge between them. There is (2,1) so add 1 to traingle count.
Repeat for vertices 1,2,4. your triangle count will be 3. Divide by 3 and you will get 1 which is the answer.
Create 2 sorted arrays.
- Rincer July 11, 2014Array 1 contains all the people with 0 taller people in front of them, sorted by height shortest to tallest
Array 2 contains all the people with 1 or more taller people in front of them also sorted by height tallest to shortest.
Insert people from Array 2 into Array 1 in a position where they have the correct number of taller people in front of them.