[algogeeks] Re: combinations problem
knapsack typically tries to maximize one attribute while minimizing some other (or optimal max for both or similar such conditions)... for this problem, all we need to do is find one subset that adds up to the given number... there's no second criteria to maximize/minimize... Please correct me if my understanding of knapsack is wrong... On Dec 29 2010, 8:01 am, juver++ avpostni...@gmail.com wrote: Yes, and this subset can be find using DP (which is cimular to 0-1 knapsack problem). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: combinations problem
As I've stated, problem is similar to the 0-1 knapsack. Find subset of elements which sums up to a given value. Possible transitions - to take or not to take particular element. That's why it's 0-1 knspsack. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: combinations problem
Is'nt this just a knapsack problem! On Dec 29, 3:45 pm, rajeev kumar rajeevprasa...@gmail.com wrote: you are given a string.It may have repeated characters.each character has it's own weight.find combination of characters whose sum value is equal to given value. ex: given string 'abcbacbabcc' weight of each character a-5,b-4,c-6. character combination which gives sum 15 is 'aaa' -- Thank You -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: combinations problem
String gives no of occurrences of each character.no of times you select a character should be less than the no of times it appears in the string. ex: given string 'abcbacbabcc' has 3 a's, 4b's, 4 c's. resulting string should have a less than 3 times,b less than 4 times and c less than 4 times. On Wed, Dec 29, 2010 at 4:25 PM, vishal raja vishal.ge...@gmail.com wrote: What's the relation with the given string. I could'nt get you completely. On Wed, Dec 29, 2010 at 4:18 PM, suhash suhash.venkat...@gmail.comwrote: Is'nt this just a knapsack problem! On Dec 29, 3:45 pm, rajeev kumar rajeevprasa...@gmail.com wrote: you are given a string.It may have repeated characters.each character has it's own weight.find combination of characters whose sum value is equal to given value. ex: given string 'abcbacbabcc' weight of each character a-5,b-4,c-6. character combination which gives sum 15 is 'aaa' -- Thank You -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thank You Rajeev Kumar -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: combinations problem
It's a knapsack problem with bounds. Solve it using DP - for each state keep number of used characters and preserve to exceed the bounds. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: combinations problem
@juver++ can you elaborate this sentence 'It's a knapsack problem with bounds. Solve it using DP' or send me any link which has good explanation. On Wed, Dec 29, 2010 at 4:52 PM, vishal raja vishal.ge...@gmail.com wrote: i think we don't need to store the total no. of occurance of any character. we can think of it as a classic knapSack, We have n ( size of the string) items, does'nt matter if they repeat or not . We don't have to keep a track how many of a char we have used as we have only options in this array , just take every index item as different item, that will automatcally do this. On Wed, Dec 29, 2010 at 4:46 PM, juver++ avpostni...@gmail.com wrote: It's a knapsack problem with bounds. Solve it using DP - for each state keep number of used characters and preserve to exceed the bounds. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thank You Rajeev Kumar -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: combinations problem
Yes, it's true. But we should process DP in the following order not to take one element more than once. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: combinations problem
@juver, ofcourse , and that's not a big deal. On Wed, Dec 29, 2010 at 5:11 PM, juver++ avpostni...@gmail.com wrote: Yes, it's true. But we should process DP in the following order not to take one element more than once. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: combinations problem
dp[i][j] - true, if there is a way to have sum j after processing the first i elements, and false otherwise. so transitions wil be: dp[i][j] = dp[i - 1][j] OR dp[i - 1][j - weight[i]], (OR means logical or),first term means that we don't want to use i-th character, second - we use it, so the sum decreases. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: combinations problem
It's not a big problem when you use 2D matrix instead of 1D for the DP :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: combinations problem
isn't it an application of association rule mining. http://en.wikipedia.org/wiki/Association_rule just that ARM will mostly result multiple solution depending on your data. Its up to you to decide a strategy for breaking ties. On Aug 15, 1:19 am, Geoffrey Summerhayes [EMAIL PROTECTED] wrote: On Aug 14, 4:25 am, sfl [EMAIL PROTECTED] wrote: Hi, Let's suppose we search into a table for N parameters, starting from a maximized key. If we do not find anything we start to generalize the key by take off one parameter. We do this until we find something. Stop. This is a poor specification, give this to 5 different programmers and expect 5 programs that give different results. Let's try with an example, 3 parameters: Database table MyTable code | state | color | size rule1 california blue large rule2 california yellow medium rule3 california yellow - rule4 california - small rule5 - - small rule6 - yellow medium Now suppose our key K is composed from K(california, red, small) We have to find the rule by search into MyTable. step1: search MyTable for (california,red,small) we do not find anything step2: search MyTable for K(california,red, null) ( we have reduced the key). Why? If you get an answer set that matches [california,red] you end up ignoring the answers to [california,small] and [small,red] both of which match using the same number of criteria but return a different set of rules. What makes the [california,red] answer set deserve special treatment? we do not find anything step3: use the K(null,red,small), we do not find anything again, step over step4: use the K(california, null, small) we finally find rule4, stop! We got to the end, but let's now suppose this row in our table: rule7 - red small step3 would find the rule7 and step4 would find rule4, which is right? If parameters has no weight, the algorithm returns 2 solution. So, suppose I give a grid of combination, ordered. ord state color size 1 x x x 2 x x - 3 x - x 4 - x x 5 - x - 6 x - - 7 - - x 8 - - - I search for K(x,x,x), then K(x,x,null) etc until I find a rule. Complexity is O(2^n) where n= number of parameters #(state,color,size)=3 If it was O(2^n) then adding 500 rules to that database wouldn't change anything, right? So, to keep it short, how would you solve this problem? Probably by going through the rules in one pass, keeping the best matching set. Which is the class of this problem? n,p,np,np-c,etc... If n is the total number of elements considered, that is the number of rules multiplied by the number of parameters, it's linear. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
