@Piyush:.. nope is not correct ...
this is right
0 1 2 3
0 1 0 0 0
1 1 0 1 0
2 1 0 1 0
3 1 0 1 0
4 1 0 1 0
use this code to precompute..
A[i,j] = A[i-1, j];
if ( A[i, j] == 0 and j - W[i] >=0)
A[i, j] = A[i -1, j - W[i]];
On Tue, Jan 10, 2012
How to create the lookup table?
say if I have W = {2, 4, 6, 8} and Wmax = 3
0 1 2 3
0 1 0 0 0
1 1 1 1 0
2 1 1 1 1
3 1 1 1 1
4 1 1 1 1
Is this correct???
On Mon, Jan 9, 2012 at 2:55 PM, Lucifer wrote:
> @All
>
> The same algo will work for both +ve a
@All
The same algo will work for both +ve and -ve nos.. no need for
modification..
For ex-
Say the sum is 4 and the set is { 1, 2, 3, -2 }
Now if u include -2 as part of ur solution then for the rest 3
elements the sum would be 4-(-2) = 6, which is correct...
On Jan 9, 2:20 pm, Siddhartha wro
yup...that was what i was thinking... i guess for negative nos, we can
define Wmax= sum of modulus of weights,and then the same algo works...
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@goog
@Siddhartha : i dont think so this will work for -ve number because we are
doing A[ i - 1, j - W[i] ] so if W[i] is -ve number then it would increases
Wmax which is the number of column.
i guess same algo can be modified so as to make it work for -ve number.
On Mon, Jan 9, 2012 at 2:23 PM, Siddh
@lucifer and others: does this work for negative elements? What to do
then???
--
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
algo
@Lucifer : got it ..nice and clear :) :).
On Sun, Jan 8, 2012 at 10:05 AM, Lucifer wrote:
> @atul..
>
> The table is used to record the state of subsets not print them.. (I
> am assuming that's what u meant)..Hence keeping that in mind, yes it
> captures all subsets... Now once A[N, K] is 1 tha
@atul..
The table is used to record the state of subsets not print them.. (I
am assuming that's what u meant)..Hence keeping that in mind, yes it
captures all subsets... Now once A[N, K] is 1 that means there are
some subsets whose sum will be equal to K. Hence, to find all such
subsets we will ba
any comments of the following approach.
first sort the weights,
find the 'j' such that sum( wts from w1 until wj) < Wmax & sum( wts from W1
until Wj+1) > Wmax
also 'k' such that sum(wts from Wk to Wn) < Wmax & sum(wts from Wk-1 to Wn)
> Wmax
so, a = j ( is the max number of elements in any sub
@Lucifer :
for W[]={1,3,2,1,2} and Wmax=4.
this array will be formed.
0
1
2
3
4
0
1
0
0
0
0
1
1
1
0
0
0
3
1
1
0
1
1
2
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
is it printing all subset ?? if yes then may be i am not getting it..
btw one query :-
b) if A
@atul..
Its an explanation of the logic not the actual code...
You can use the following code to implement the same..
A[i,j] = A[i-1, j];
if ( A[i, j] == 0 and j - W[i] >=0)
A[i, j] = A[i -1, j - W[i]];
On Jan 7, 9:45 pm, atul anand wrote:
> @Lucifer : thats okbut you are using bitwise O
@Lucifer : thats okbut you are using bitwise OR to fill up the array
A[].
if condition does not fullfill then wat to do to fill A[i,j] ??
i guess take it 0 if it does not fullfill..
A[i , j] = A[i-1, j] | 0 // A[ i-1 , j - W[i] ] check fail
i didnt read your whole algorithm so i am
@atul..
I thought that check would be obvious as i didn't put in the code.. so
when the code is written for the second option we need to also check
for j-W[i] >=0..
:)...
On Jan 7, 9:15 pm, atul007 wrote:
> @Lucifier:
>
> i guess you made some editing mistake :-
>
> Initialize the array with the
@Lucifier:
i guess you made some editing mistake :-
Initialize the array with the following values,
1) A[0, j] = 0 for 1 <= j <= Wmax
2) A[i, 0] = 1 for 0 <= i <= Wmax // it shoud be 1 for 0 <= i <=N
about this equation :-
A[i , j] = A[i-1, j] | A[ i-1 , j - W[i] ]
say if W[i]=10 and j=3
I have modified some part of the above post below to avoid confusion
regarding the generation of all subsets:
Say, we need to find all the subsets which led to A[N, K] = 1, to do
this we will take the following steps :
a) If ( i == 0 ) print the subset and return.
b) if A[N -1 , K] = 1,
b
I have an idea, i think it can be done in O(N * Wmax).
Let the weight array be W[N].
Take an array A[N][Wmax] , where N is the no. of weights provided and
Wmax is the max weight.
Initialize the array with the following values,
1) A[0, j] = 0 for 1 <= j <= Wmax
2) A[i, 0] = 1 for 0 <= i <= Wma
@piyuesh 3-Sum is not exponential ? its quadratic , check wiki for refrence
?
On Mon, Dec 5, 2011 at 5:36 PM, Piyush Grover wrote:
> As I mentioned earlier solution with exponential time-complexity is the
> obvious one. Is there any way to solve this problem by greedy/Dynamic algo?
>
>
> On Mon,
As I mentioned earlier solution with exponential time-complexity is the
obvious one. Is there any way to solve this problem by greedy/Dynamic algo?
On Mon, Dec 5, 2011 at 5:24 PM, WgpShashank wrote:
> @piyuesh , Saurabh isn't 3-Sum Suffics Here ?
>
> Another thought problem can also be thought by
@piyuesh , Saurabh isn't 3-Sum Suffics Here ?
Another thought problem can also be thought by generating power set of
given set e.g. if set has n elemnts its power set has 2^n elements , then
finds the set that has sum up yo given weight isn't it ? hope you know how
to find power set efficien
As such there's no significance for Vi, it's just to show that objects are
not identical. We don't need to maximize on V. For the sake of problem you
can ignore it. We can use the sum of values for other purpose.
Take an examole: S= {1, 2, 3, 4, 5} are weights (I am not using Values)
. Wmax = 8
S
@ Piyush..
I have a doubt... Is there any significance of the value Vi, if yes
then can u give an example.
If not, then is your question about finding all maximum subsets where
the addition of the weights results in maximum (each weight being
considered only once)...
Say for ex-
The max weight is
21 matches
Mail list logo
