Whats wrong with the following program?

[Nikhar]

The question is-

Choosing chocolates

Santa Claus has lined up a row of bowls, each containing some chocolates. Nikhil has been told that he can pick up as many of these bowls as he wants, provided that he never picks two consecutive bowls.

Your aim is to help Nikhil choose a set of bowls so that he maximizes the number of chocolates that he picks up.
Input format

The first line of the input contains one integer N, the number of bowls. This is followed by a line containing N integers, describing the number of chocolates in each of the N bowls.
Notes

In all cases, N ≤ 100,000.
Output format

Your output should be a single line consisting of one integer, the maximum number of chocolates that Nikhil can collect.
Sample Input

10
30 10 8 20 11 12 25 13 20 19

Sample Output

95

This is my solution:-

#include<iostream>
#include<map>
#include<queue>
#include<deque>
#include<algorithm>
#include<list>

using namespace std;

typedef unsigned long int uli;

 uli maxweight1,maxwieght2;

struct vertex;

struct edge
{
    vertex *dest;
    edge():dest(NULL){};
};

struct vertex
{
    uli quantity;
    vector<edge> adj;
    uli dist;
    int scratch;
    bool mark;
    vertex():quantity(0),mark(false),dist(0),scratch(0){};
    vertex(uli a):quantity(a),mark(false),dist(a),scratch(0){};
};

class graph
{
    public:
    vector<vertex> vecver;

    void makegraph(deque<uli> &);
    void findedges(const uli &);
    void maxweight();
    void acyclic();
};


void graph::makegraph(deque<uli> &deq)
{
    uli temp;
    while(deq.size()!=0)
    {
        temp=deq.front();
        deq.pop_front();
        vertex *v= new vertex(temp);
        edge e;
        e.dest=new vertex(deq[1]);
        v->adj.push_back(e);
        e.dest=new vertex(deq[2]);
        v->adj.push_back(e);
        vecver.push_back(*v);
    }
    int i=vecver.size()-3;
    vertex v=vecver[i];
    v.adj.pop_back();
    i+=1;
    v=vecver[i];
    v.adj.pop_back();
     v.adj.pop_back();
    i+=1;
    v=vecver[i];
     v.adj.pop_back();
    v.adj.pop_back();
}

void graph::findedges(const uli &a)
{
    vector<vertex>::iterator itr;
    for(itr=vecver.begin();itr!=vecver.end();itr++)
    {
        if(a==(*itr).quantity)
            break;
    }
    if(itr==vecver.end())
        cout<<endl<<"Node doesn't exist!";
    else
    {
        vertex v=*itr;
        edge e=v.adj[0];
        vertex *w=e.dest;
        cout<<w->quantity<<endl;
        e=v.adj[1];
        w=e.dest;
        cout<<w->quantity;
    }
}

void graph::acyclic()
{
    vector<vertex>::iterator itr=vecver.begin();
    list<vertex> q;
    for(;itr!=vecver.end();itr++)
    {
        vertex v=*itr;
        for(int i=0;i<2;i++)
            v.adj[i].dest->scratch++;
    }
    for(itr = vecver.begin(); itr!=vecver.end(); itr++)
    {
        vertex v = (*itr);
        if ( v.scratch == 0 )
        q.push_back( v ) ;
    }
    for(;!q.empty() ;)
    {
        vertex v = q.front( ) ; q.pop_front( ) ;
        for( int i = 0; i < v.adj.size( ) ; i++ )
        {
            edge e = v.adj [ i ];
            vertex *w = e.dest;

            if( --w->scratch == 0 )
            q.push_back(*w) ;


            uli cvw = w->quantity;
            if( w->dist < v.dist + cvw )
            {
                w->dist = v.dist + cvw;
            }

        }

    }
    if(vecver[vecver.size()-1].dist>vecver[vecver.size()-2].dist)
        cout<<vecver[vecver.size()-1].dist;
    else
        cout<<vecver[vecver.size()-2].dist;
}


int main()
{
    int size;
    graph g;
    uli x;
    deque<uli> deq;
    cout<<"\nEnter the number of bowls:-";
    cin>>size;
    cout<<"\nEnter the elements:-";
    for(int i=0;i<=size-1;i++)
    {
        cin>>x;
        deq.push_back(x);
    }
    g.makegraph(deq);
    g.acyclic();
}

I have used the following algorithm:-
I made a graph out of the input.Logically if Nikhil has currently picked the ith element, then he should pick the i+2 or the i+3 element. So, I have made each input as a vertex and an edge between i and i+2, i and i+3.

I made the function find edges to see if my program was working correctly so far. And it was!

Now, it came to finding the maximum weight. Now, I did topological sorting based on incoming edges by scratching them. Since, we can only have 2 input edges, the maximum value of scratch is 2.

Now, based on the sorting I performed the following operation. If the current 'dist' is less than the 'dist' of previous vertex plus the quantity of the current vertex, update the current vertex.

Eventually, as we know, the maximum number of choclates that he can pick is in either the last or the second last vertex member dist.

So, I'm printing the greater of the two. But my program is outputting the last element.

Where did I go wrong?

[jsmith]

I'm sorry Nikhar, for me to help you with the above code would require me to have access to
a compiler which I don't right now.

But, I think you can solve this problem in a manner similar to the solution I last gave you for
the other problem, by starting at the end and working backwards to the beginning.

[Nikhar]

The above code is compiled in code::blocks.

I know the solution that you gave would work. But I wanted to know if my algorithm was correct.

[Disch]

Either I'm misunderstanding the problem, or your example output is wrong.

as far as I can tell, it's possible to pick up all bowls except for 1. Given the original problem:

There are a total of 168 chocolates in 10 bowls. From what I see, you can pick up all except the '8' bowl, giving you 160 chocloates (not 95 as the example solution states).

How I did it:

bowls   30  10   8  20  11  12  25  13  20  19
picked   7   9   -   5   2   8   4   6   1   3

As you can see I never picked any 2 consecutive bowls, and got all of them except the 8.

Maybe the solution is as simple as summing the bowls and subtracting the smallest bowl (that isn't on an outer edge) from the sum? I find that doubtful though.

But anyway before I can help solve the puzzle I need to make sure I understand what the puzzle is. As of right now I think I must be misunderstanding since I got different results than the example.


EDIT: oh wait... I did misunderstand...

for some reason I thought you meant you can't pick a bowl that was adjacent to the bowl you picked previously.

But now I see what you mean.

Okay that's much simpler... hang on...

[Nikhar]

yeah..waiting. :)