hey utkarsh i can't understand your algorithm cn u explain it
again
On Aug 6, 11:34 pm, UTKARSH SRIVASTAV wrote:
> My accepted solution is this and I have told you my logic
>
> #include
> struct node
> {
> int data;
> int add;
> struct node *next;}*front,*rear;
>
>
My accepted solution is this and I have told you my logic
#include
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 node));
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 wrote:
> http://www.spoj.pl/SPOJ/problems/TUG/
>
> earlier i thought it would be easy to do it knapsack...but when
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 form
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 =
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 wrote:
> original knapsack is called fractional knapsack in which greedy works...but
> we were ta
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
wrote:
>
>
> On Thu, Aug 4, 2011 at 8:13 PM, saur
On Thu, Aug 4, 2011 at 8:13 PM, saurabh singh 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 in reasonable tim
@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 theorit
@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
wrote:
> On Thu, Aug 4, 2011 at 7:42
On Thu, Aug 4, 2011 at 7:42 PM, Gaurav Menghani
wrote:
>
> On Thu, Aug 4, 2011 at 7:37 PM, saurabh singh 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'
>
On Thu, Aug 4, 2011 at 7:37 PM, saurabh singh 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 polynomial-time algorit
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 as
@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 startwhi
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 algogeeks@
@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
>
>> when i said pick elements in descending order,it meant sorting them.Sorry
>> for being unclear.
>> Bu
Classic problem of DP + bit´s...like knapsack
2011/7/30 saurabh singh
> 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.
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 wrote:
> @Amol according to my
@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 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 respective
> partitions.
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 ther
20 matches
Mail list logo
