hey utkarsh i can't understand your algorithm cn u explain it
again
On Aug 6, 11:34 pm, UTKARSH SRIVASTAV usrivastav...@gmail.com wrote:
My accepted solution is this and I have told you my logic
#includestdio.h
struct node
{
int data;
int add;
struct node
http://www.spoj.pl/SPOJ/problems/TUG/
earlier i thought it would be easy to do it knapsack...but when i started
coding iti feel lost.i have failed to relate it with 0/1
knapsack..
plz tell me how this problem can be solved using dp solution of
knapsack..i mean in knapsack you
anyone plz give hint how to solve this problem !!
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
On Sat, Aug 6, 2011 at 2:53 PM, Amol Sharma amolsharm...@gmail.com wrote:
http://www.spoj.pl/SPOJ/problems/TUG/
earlier i thought it would be easy to do it
My accepted solution is this and I have told you my logic
#includestdio.h
struct node
{
int data;
int add;
struct node *next;
}*front,*rear;
int flag,c;
int fun(int item)
{
struct node *temp,*temp2,*r,*p,*q;
int k,i;
r=(struct node*)malloc(sizeof(struct
@saurabh: see this case
input 100, 1, 1, 1,1
your algo -
group 1 - 100
group 2 - 1 1 1 1
but the group with 2 equal strength can be formed as
G1 - 1 1
G2 - 1 1 or 1 1 each...
i mean it is not necessary to take all the people.but your algo takes
the the person with max strength at
Hence shown never play cricket when someone in the group is stronger than
the whole team together,,,:D
Anyways my original solution was not taking into account that players can be
excluded.(Thats unfair in a real scenario ryt?)
Its a classical 0/1 knapsack problem which can be implemented either
On Thu, Aug 4, 2011 at 7:37 PM, saurabh singh saurab...@gmail.com wrote:
Its a classical 0/1 knapsack problem which can be implemented either as a
greedy solution or dp
It has been stated earlier in the thread that this is an 'NP-Complete'
problem. [0]
It means, there is no known
On Thu, Aug 4, 2011 at 7:42 PM, Gaurav Menghani
gaurav.mengh...@gmail.com wrote:
On Thu, Aug 4, 2011 at 7:37 PM, saurabh singh saurab...@gmail.com wrote:
Its a classical 0/1 knapsack problem which can be implemented either as a
greedy solution or dp
It has been stated earlier in the
@gaurav: agree...greedy wouldn't work in this case..even 0-1 knapsack is
a DP problem...which can't be done by greedy !!
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
On Thu, Aug 4, 2011 at 7:46 PM, Gaurav Menghani
gaurav.mengh...@gmail.comwrote:
On
@amol knapsack is originaly a greedy problem onlyThe spirit remains
the same,selecting the best at each stepDp helps in defining the best in
the particular case.
@Gaurav I think its NP complete once the number of teams become
varaible,
corrct me if wrong i am weak with the
On Thu, Aug 4, 2011 at 8:13 PM, saurabh singh saurab...@gmail.com wrote:
think its NP complete once the number of teams become varaible,
corrct me if wrong i am weak with the theoritical stuffs...
Err, it is NP-complete, the thing is when the set of integers is small, a DP
solution runs
original knapsack is called fractional knapsack in which greedy works...but
we were talking abt 0-1 knapsack :P
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
On Thu, Aug 4, 2011 at 8:19 PM, Gaurav Menghani
gaurav.mengh...@gmail.comwrote:
On Thu, Aug
I told you the spirit is greedy backed up by DP for creating correct optimal
substructuresA pure greedy solution wont create the right
substructure...
On Thu, Aug 4, 2011 at 9:06 PM, Amol Sharma amolsharm...@gmail.com wrote:
original knapsack is called fractional knapsack in which greedy
As some have said, this is NP, so for larger values of N it takes a
very long time. For N=20 it runs quite quickly.
// True if some set of strengths from s[n] sum to t
bool divide(unsigned int *s, int n, int t)
{
if (t == 0) return true; // We reached the goal
if (n
Can you explain a bit more?
Thanks
Nitish Garg
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/-LiQq0dHHksJ.
To post to this group, send email to
To Solve This Problem, I would
1. Sort the given list S by their respective strengths.
2. Then I would create two other lists A and B for respective
partitions.
3. (a) Remove First and Last from S add them both to A
(b) Remove First and Last from S add them both to B
4. Repeat Step 3 until
@Amol according to my algo
group 1=9 4 3
group 2= 7 8 1
Think again
On Sat, Jul 30, 2011 at 6:27 PM, Gary Drocella gdroc...@gmail.com wrote:
To Solve This Problem, I would
1. Sort the given list S by their respective strengths.
2. Then I would create two other lists A and B for
when i said pick elements in descending order,it meant sorting them.Sorry
for being unclear.
But i am open to any discussion about my logic because its pure intuition
based algo,so it may be having lots of loop holes.
On Sun, Jul 31, 2011 at 7:02 AM, saurabh singh saurab...@gmail.com wrote:
Classic problem of DP + bit´s...like knapsack
2011/7/30 saurabh singh saurab...@gmail.com
when i said pick elements in descending order,it meant sorting them.Sorry
for being unclear.
But i am open to any discussion about my logic because its pure intuition
based algo,so it may be having lots
@victor +1
On Sun, Jul 31, 2011 at 8:12 AM, Victor Manuel Grijalva Altamirano
kavic1.mar...@gmail.com wrote:
Classic problem of DP + bit´s...like knapsack
2011/7/30 saurabh singh saurab...@gmail.com
when i said pick elements in descending order,it meant sorting them.Sorry
for being
20 matches
Mail list logo