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
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
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
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.
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
@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
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
@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
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
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
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
11 matches
Mail list logo
