|
Hello,
I want ask you to read my algorithm for solving Knapsack Problem and tell me if i'm wrong or if there is similar algorithm
If you are interested, i can send you source code, description and etc.
Knapsack problem algorithm.
Nikolay Nedelchev Bulgaria, Sofia e-mail :
I. Integer item weight.
Let's review how the DP algorithm works and focus on the important points.
Let N be the item count, and M - the capacity of the knapsack. The DP algorithm constructs a table with dimensions M * N, and calculates for EVERY possible knapsack with capacity <= M all N possible solutions, for items (1), (1,2), (1,2,3)..(1,2..N), i.e Omega(M*N).
One of the bigger problems with this algorithm is that in practise it has to solve "similar problems", which give one and the same solution. Because knapsacks with capacities M-4 and M-5 can have identical solutions, but the DP algorithm has to calculate them both, no matter what.
Let's have a completely different look at the knapsack problem.
Let's ask ourselves how many knapsacks which are smaller or equal in capacity than M and have ONLY DIFFERENT BEST SOLUTIONS, exist(solutions with different total value and weight, all solutions with equal total weight and value are considered as a single solution, and only one of them is used, no matter which). Let these different solutions form the set S.
It's obvious that the size of S is <= M (eg: if M = 1000, there is no way that 1001 problems with different solutions exist, when there are 1000 possible knapsack capacities {M=1000})
Let's also note that the solution from S with largest value (and it's also the one with largest weight, because if a solution with greater weight and smaller value existed, it wouldn't be present in the set, because it wouldn’t be BEST solution for any knapsack) will be our solution for knapsack with capacity M.
This means that if we can build the set S with time and space complexity O(S*N) in sorted form, we can get to the solution of the initial problem by another O(1) operations and because S <= M, this algorithm would be better or at least equal (in the special cases) to the DP algorithm.
The Algorithm:
Let’s have a set of objects O={oi}, i = 1,2…n each object having a weight and value.
Let’s have a set of objects S = {si}, I = 1,2..m, each object being an unique subset of O.
Each object of S has value which is the total value of all the objects oi in the represented subset of O, and weight, formed in the same way.
S contains:
1. Every subset of O except those which have a smaller value than at least one of the other subsets with the same or smaller weights. (and except those which have same value with at least one of the other subsets with the smaller weights)
see Clarification
2. Only one of the subsets with exact same weights and values, no matter which.
Let S be sorted by descending weights.
The so formed set S, has the following properties:
Property A: The so defined set S contains all the possible best answers for all the possible knapsacks for which there is a valid solution.
Property B: Each object in S is the best answer for at least one possible knapsack.
Property C: The list is sorted by weight.
Property D: The list is sorted by value (because of 1.).
Let’s have a new object p of type O.
Let’s have a new set T = {ti} of type S, which contains all the objects from S, but each subset is augmented with the object p, so the value of each object of T, ti , is equal to the value of si plus the value of p. The same applies to the weight.
T has all the same properties A(*), B(*), C, D.
Let’s add p to T, as a singular subset in the right position, in order to preserve the sort order by weight.
The so formed set T has lost properties B and D, but has kept properties A(*) and C.
* It follows from Prop A, that the set T contains the solutions to all the possible knapsacks if t should be present in the solution.
As a reminder, S contains all the solutions if t should not be present.
So, we can create a new set S, which is formed from merging the old S and T, keeping with 1. and 2.
The new set S has all the properties A.B.C and D for the new set O including object p.
The time complexity of the construction of the new set S takes O(N) time, with N being equal to the size of the old set S.
If at the time of the execution of the so presented algorithm, all the O objects and the capacity of the knapsack are known, all the sets S can be optimized according to the currently found best solution and input information, i.e. we can add to points 1. and 2. a new point 3. That the weight of the subsets in S does not exceed the capacity of the knapsack and etc.
Because all the operations described here on S take a linear time, it follows that the overall time complexity of the algorithm is O(S1+S2+S3…SN) (the sum of the sizes of all the sets S i.e. from definition of S : m1 + m2… mn) .
Clarification to 1.
If we have o1(w = 2, v = 9) and o2(w = 4, v = 8).
Then S = { s1 = (o1) , s2 = ( o1 + o2) }
We do not need the o2 object as a singular subset and will never need the o2 object in a subset that does not contain the o1 object
NOTES:
1. With a suitable representation in memory, every object in S can take constant space and the solution can be extracted in O(n) time, n = size of solution. Also in general there is no need to keep all objects of all sets S.
2. If we compare this algorithm to the currently available dynamic programming algorithms we will note that the sum of all the sizes sets S which we have created, is smaller or equal to the size of the table, which we would have allocated (and calculated) during DP, in other words, the time and space complexities of the algorithm are always smaller or equal to the complexity of the DP algorithms
3. The algorithm can be used with all kinds of input data, including real, negative (as well as very big), etc, numbers as weights.
4. We don’t need to calculate the last set of subsets S
5. The algorithm can be easily transformed to the algorithm of Horowitz and Sahni.
Please tell me about errors and other uncertainties.
modified on Friday, July 1, 2011 12:07 PM
|
|
|
|
|
Never post your email address in any forum, unless you really like spam! If anyone replies to you, you will receive an email to let you know.
Real men don't use instructions. They are only the manufacturers opinion on how to put the thing together.
Manfred R. Bihy: "Looks as if OP is learning resistant."
|
|
|
|
|
Hi all,
I am sure there are loads of samples around but I am really not finding a relevant one for some reasons (perhaps it's a Friday brain melt thing)
I have two points in 3D space - I know their coordinates (x, y, z) and I know their rotations (x, y, z)
I know this should be enough information to calculate a line (is it a vector? it's been sooo long since uni  )
What I want is to calculate the point (x, y, z) where the lines intersect (if any). The Z axis is actually not important, I want an intersect point on only X and Y planes, the Z value of the point will be half way between the original 2 points Z value.
Can any shed some light, or has a link? All info I am finding doesn't seem to allow me to make use of my rotation data.
Thanks for any help
I may or may not be responsible for my own actions
|
|
|
|
|
Here is a very good tutorial[^], section 2 has what I think you're looking for. It deals mostly with 2D, but it is easily extended to 3D.
In general, I highly recommend TopCoder's tutorials on algorithms: very down-to-earth, they are often written by highly skilled "competition programmers" for other "competition programmers" (as opposed to typical coursework written by professors for students, often loaded with very important and equally boring details).
|
|
|
|
|
Thanks I will take a look into this
I may or may not be responsible for my own actions
|
|
|
|
|
I think we need a bit more information; you've said that you have two points in 3-space, but want to calculate the intersection of two lines. That does not compute, Will Robinson. Do you have equations for your two lines? If so, let one line be f(x,y,z) and the other g(x,y,z). Use simple linear algebra to solve for x, y, and z such that f(x,y,z) - g(x,y,z) = 0. If not, you really need to clarify your question.
Will Rogers never met me.
|
|
|
|
|
the two points have rotation data which is how I consider them lines (infinitely long lines running thou the know point at the given angle)
I didn't have the line equations which turns out to be what I was actually trying to find.
I have worked it all out now anyway, but thanks for the reply
I may or may not be responsible for my own actions
|
|
|
|
|
In general, lines in 3D do not intersect. The closest thing is the line-line closest approach[^] which is too complex to explain here, but that article is good.
The Z axis is actually not important, I want an intersect point on only X and Y planes
This leads me to believe that you actually want 2D line intersection. There are a number of ways to formulate that but a nice one is using the line equations:
Line 1 = (a1,b1) + k1(dx1,dy1) =>
x1 = a1 + k1.dx1 and
y1 = b1 + k1.dy1
Line 2 = (a2,b2) + k2(dx2,dy2) =>
x2 = a2 + k2.dx2 and
y2 = b2 + k2.dy2
Target: L1 = L2 =>
a1 + k1.dx1 = a2 + k2.dx2
b1 + k1.dy1 = b2 + k2.dy2
There are only four unknowns (k1 and k2, and the meeting point (x1,x2)). The bottom two equations eliminate the coordinates leaving two equations and two unknowns. Now eliminate k2 (k2 = (k1.dy1 + b1 - b2)/dy2):
a1 + k1.dx1 = a2 + (dx2/dy2)(k1.dy1 + b1 - b2)
k1(dx1 - [dx2.dy1/dy2]) = a2 + (dx2/dy2)(b1 - b2)
k1 = [a2 + (dx2/dy2)(b1 - b2)] / (dx1 - [dx2.dy1/dy2])
Looks complex, but all those quantities are known at the start, so you can calculate k1 (unless dy2 is 0, in which case special case it, or the whole right hand side is 0, in which case the lines are parallel and there is no intersection).
Then you can use the k1 to calculate k2 from either of the last two equations, and then use k1 and k2 to find the intersection point. Note that if k1 or k2 is < 0 the intersection is 'before' the 'beginning' of the respective line; you may want to count such cases as failures, depending on the problem (and similarly for k > 1).
(NB I didn't check that maths, there may be a mistake, but the principle is sound.)
|
|
|
|
|
Thanks for the reply. I have solved this already now thou.
I did just want 2D intersection which is why I said the Z axis is not important, I can take a middle ground value for the resulting Z co-ordinate. The part I was really trying to find out (as it turns out) is to determine the line equations from the data I had.
For this I used cosine and sine methods to calculate a "second point" for each "line". From this I could then calculate the slope (m) and y-intersect (b) for my line equations. Then I solve the equations to get the intersect point. simple when you know how 
I may or may not be responsible for my own actions
|
|
|
|
|
NOTE: Please let me know if another section/forum on the site is more appropriate for this question.
I'm trying to solve an algorithm puzzle and I was hoping to get some help. Its not for any formal study, just a mind exercise/ puzzle but I've hit a road block:
The goal is to figure out what algorithm or formula can be used to decrypt and encrypted string of characters where you know the characters being encrypted and what their encrypted value is but not how the encrypted value is determined. Obviously this would be like looking for a needle in a haystack except that there are some parameters to this that help (I think) narrow the process down. I can't help but think there's got to be a pattermn or method for figuring out something like this when you know the values of both the unencrypted character and what it encrypts to.
The parameters of the puzzle are:
1) The encrypted characters are limited to the printiable set of characters within the standard 256 character ASCII set of characters (basically what's on a standard US keyboard). I suppose the thing woiuld work with non-visible charactres but I believe the intent is to use any of the keyboard characters a user could use and so that would include numbers, letters and some of the special characters too.
2) the string of characters to encrypt is limited to 12.
3) Each single character is encrypted to a 2 character value (I think it's always a number but I'm not certain ) so that a string of 12 characters will be encrypted to a 24 character long value.
4) Each character is encrypted to the exact same value based on its position in the string of characters to be encrypted.
For example if the text to encrypt is abcdefga1234 then the lower case a is encrypted to the value 57 for position 01 in this string of 12 characters and in the 8th position the lower case a is encrypted to a value of 0A.
No matter what combination of characters are in positions 1 thru 7, the lowercase a will always been encrypted as 0A when it is in the 8th position in the string of characters.
5) Each combination of characters plus position has a unique encrypted value and that value is constant when the position of the character is the same.
I hope the last 2 above make sense; it's hard to convey these in words.
I know that a large lookup table of characters along with their decrypted values and position could be sued to decrypt an encrypted string but unfortunately that’s not the answer to the puzzle. The goal is to decipher what formula or algorithm will decrypt an encrypted character using the above parameters.
If anyone has any links or suggested reading material on how to solve something like this I would most appreciate it.
|
|
|
|
|
Ok let's see if I can come up with something, sounds fun!
The hints we can gather from the given puzzle parameters are:
1) It seems we're talking ASCII characters, one byte per character and a well-known codification.
2) A maximum length of 12 chars, ok.
3) Putting together this with what I see in point 4, it seems the encrypted 2-character data seems to represent a byte value in hex (examples are "57" an "0A", both valid hex byte values).
4) So, the character position in the input string is the second variable to take into account (the first is the character ASCII code itself, see point 1).
5) This confirms what I said for points 1, 3 and 4.
So, we want to find an operation "op" which, applied to the two variables (character code and position) gives us the resulting hex code.
Now let's have a look at the examples we find in point 4.
We know that the ASCII code for "a" is decimal 97, hex 61h, so:
61h op 01h = 57h
61h op 08h = 0Ah
(where 01h and 08h are the character positions in the example, of course)
Let's have it in binary and decimal too, it will be useful:
0110 0001 op 0000 0001 = 0101 0111
0110 0001 op 0000 1000 = 0000 1010
97 op 1 = 87
97 op 8 = 10
Now, one interesting thing we can see is there seems to be a symmetrical relation between the three values:
97 - 10 = 87
This hints at a relation where the only variable is the character position (1 or 8).
So, let't try to find an operation which transforms our equation system in:
97 - 10 = 87
97 - 87 = 10
Looking at the binary representation of 87 and 10, I can seen that if I shift 87 three digits to the right I obtain 10 (0101 0111 shr 3 = 0000 1010).
So, one possibile solution for the puzzle is:
1) Take the charater's ASCII code ("a" = 97)
2) Subtract 10 (97 - 10 = 87)
3) Shift the resulting byte to the right by a number of digits equal to the character's position plus 2, where the first position in the input string is 1, but if the number of digits to shift is 10 or more, subtract 10. (so, 1 + 2 = 3 -> shr 3 ; 8 + 2 = 10 -> 10 - 10 = 0 -> shr 0).
3) Subtract the resulting byte from the character's ASCII code (so, 97 - 10 = 87 ; 97 - 87 = 10).
While this works for the two given examples, it's a very weak explanation. For example, what I say in point 3 can work in other ways too, and still give the correct results.
Maybe someone who is more experienced in cryptography than me will come up with a better solution.
Hope this can somehow help you, it sure was fun for me! 
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
In general, it is not doable: consider what happens when "a large lookup table" that you describe in your post is filled with randomly generated unique entries. Your target alphabet easily accommodates this, so the result satisfies each of your criteria 1 though 5. Yet the only way to "crack" this "pattern" would be to record the entire lookup table.
|
|
|
|
|
Clearly a very basic algorithm if each character is changed individually. I would say it is just a shift cipher of some sort.
First convert the characters to hex
a b c d e f g a 1 2 3 4 =
61 62 63 64 65 66 67 61 31 32 33 34
now find out what values you need to add to those to get your resulting encryption. As I only have two values to use, here is a sample
61 62 63 64 65 66 67 61 31 32 33 34
+ -10 -57
--------------------------------------------------
57 0A
fill in the rest and look for a pattern. Could be a repeating key, e.g. -10 +5 +23 - 57
interestingly (and maybe a coincidence) is that the second "a" is a reduction of the previously calculated "a"
So the algorithm could be...
1. start with a byte array of size [256] that contains all -10 values
2. loop each character
3. convert character to hex (iHex)
4. convert iHex to decimal (iDec)
5. encrypted hex (eHex) equals: iHex - bytearray[iDec]
6. set new bytearray value: bytearray[iDec] = eHex (ready for next use)
7. output eHex to result string
8. process next character
...of course that is just one possible to match the results you have given
I may or may not be responsible for my own actions
|
|
|
|
|
First off thanks to both Moreno Airoldi and musefan for providing such detailed and well thoughout replies, this is the kind of help internet forums/boards are all about.
I didn't realize how beenficial it would be to prvide additional sample values esle I would have given more then just the few I did. I am going to check out both your recomendations but it will be a day or so before I can get to them (thats why my own reply to each of you has been so slow coming) and so in the mean time here are more examples that might actually scream a pattern to you 2 who are clearly more versed in patterns.
I tried to provide a sampleing without going over board. The belwo restroicted to a,b & c (in upper & lower case) is for just the first 3 positions and the resulting number of rows is 18. To show all 12 positions for just a few characters is a lot.
Anyway, if anything about the pattern in teh eblow jumps out at you please let me know else I'll let you know what comes of testing your suggestions.
Thanks
Position, unencrypted character, encrytped value
1 a 57
2 a 24
3 a 2A
1 A 77
2 A 04
3 A 0A
1 b 54
2 b 27
3 b 29
1 B 74
2 B 07
3 B 09
1 c 55
2 c 26
3 c 28
1 C 75
2 C 06
3 C 08
|
|
|
|
|
Well obviously the same character in upper and lower case in the same position differs by (hex) 20. This strongly implies that the ANSI value of the character is being used in a relatively unsophisticated way (upper and lower case are separated by hex 20 in ANSI). The difference can be either way; to me this suggests an xor. However, it is not totally trivial as a->b->c is not just +1 each time:
(ASCII value a 61 b 62 c 63)
Slot 1 a 57 b 54 c 55
Slot 2 a 24 b 27 c 26
Slot 3 a 2A b 29 c 28
All numbers posted here are in the range 06-77. I would guess that it is a 7 bit algorithm (working on 00-7F) and operating with XORing the input character with some function of the input. Let's look at the XOR values for those slots:
Slot 1 a 36 b 36 c 36
Slot 2 a 45 b 45 c 45
Slot 3 a 4B b 4B c 4B
Looks like I'm onto something there. All that remains is to determine what the XOR parameter which is a function of position is. There isn't enough information in 3 slots and the pattern 36->45->4B does not immediately jump out at me as being meaningful. The encrypted value of 'aaaaaaaaaaaa' should provide all the XOR keys and hopefully that is enough to identify how they are calculated.
|
|
|
|
|
You beat me to it 
Your suggestion of encrypting "aaaaaaaaaaaa" should be enough to solve this you are right.
I think there is no pattern as it is just a random set of chars used to provide the XOR values, which should start with "6EK........."
I think the OP has been lucky that such a simple algorithm was decided on
If my jokes make me laugh, then I have already succeeded with 100% of my target audience
|
|
|
|
|
Well he said it was a mind exercise/puzzle, so I guess it's supposed to be solvable by a person in a reasonable time.
You may well be right that the XOR key is simply a 12 character pass code/encryption key.
Encrypting 'aaaaaaaaaaa' (or the equivalent with byte zeroes) is often useful for key analysis in simple encryption schemes. I had to modify the first version of my stream encryptor because by throwing a stream of zeroes at it, it would dispense the key. (Real life binary messages, particularly if you're using my socket library as well, often have quite a few zeroes in known places – for example if you request an EXE or DLL download you can rely on 16 or more consecutive zeroes in places in the header; and 4 byte length encoded messages will generally be possible to generate with three zeroes in known positions.)
|
|
|
|
|
Hello everybody
i am trying to disprove the claim:
the time complexity of merging K AVL trees is O(the sum of their nodes number)
i tried to calculate the complexity of meging K AVL trees but there could be more than one algorithm.
How do i disprove the claim.
Thanks
|
|
|
|
|
If you handle every node in every tree, the complexity will be O(the sum of their nodes number).
So one way to disprove this is to come up with a merging algorithm that avoids handling every node. One way to avoid handling every node is to reuse the existing structure of the AVL trees.
This can be done in trivial cases where the ranges of key values for the trees don't overlap. If they DO overlap (which is most likely), then you have a much more difficult problem, because you have to "weave" one tree into another, while maintaining the tree's balanced property.
You may be able to find subtrees whose key values don't overlap, and merge these. Using bigger building blocks like this avoids handling every node, and reduces the time complexity of your algorithm. After merging, you will probably have to do a little rearranging to restore the balanced property.
But it seems very hard, and in most cases, probably impossible.
|
|
|
|
|
If you diligently handle every node, I think the time will be O(N*Log2 N), where N is the sum of all nodes numbers.
|
|
|
|
|
To merge K trees in O(N), where N is the sum of node counts, you must never search on insertion: all your insertions must complete in O(1). In other words, on each step you must insert the new root node, and maybe do a rotation or two. However, the new root could come from any of the K trees that you are merging, so the time to search for that node would be O(K) (perhaps you could do O(Log2 K), but regardless of how you do it, K will be a factor to it). That's why I think the best you can do is O(N*Log2 K).
|
|
|
|
|
i liked that idea, lets say we've got k tree where each one got one node.
we know that there is no algorithm that can sort with better than teta(klogk) so, in order to sort the nodes in array and scan an empty tree to insert them, it will takes at least teta(klogk)
|
|
|
|
|
Who can tell me more about Eye-like Algorithm?
|
|
|
|
|
|
I don't want google I want to hear the opnion of our fulks here in CP what they have to say about this subject.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
