2 problems for u guys

[amoshag]

2 problems i'v encountered doing some job, not as easy as it may seems...

1. you are given a set of some integer numbers (some is probebly around 60-70). As integers some of the numbers are negative and some positive. You need to find maximal sub-set which the sum of it's elements it's 0 ( zero +- 1).
for ex: {-1,1,1,1,1,3,-2,-7} will have the answer of {1,1,1,1,3,-7}.

2.you got a DAG (directed acyclic graph) already topolpgical sorted. you want to find the minimum number of distinct paths that will cover all vertices of the graph. for ex: if you got a->b->c->d->e then you got one path that will cover the graph.

[tex23bm]

[QUOTE=amoshag]2 problems i'v encountered doing some job, not as easy as it may seems...

1. you are given a set of some integer numbers (some is probebly around 60-70). As integers some of the numbers are negative and some positive. You need to find maximal sub-set which the sum of it's elements it's 0 ( zero +- 1).
for ex: {-1,1,1,1,1,3,-2,-7} will have the answer of {1,1,1,1,3,-7}.

just a clarification question:

if you instead had the set {-1,1,1,1,2,3,-2,-7}

is the subset {-1,1,1,1,-2} the answer, or would it be {1,1,2,3,-7}, or both?

Tex23bm

[RoboTact]

Do you need it solved or you just share these puzzles? Second question is classic algorithm. First question is about knapsack problem and can be solved using different methods depending on if you need the precise solution.

[amoshag]

[QUOTE=tex23bm]

2 problems i'v encountered doing some job, not as easy as it may seems...

1. you are given a set of some integer numbers (some is probebly around 60-70). As integers some of the numbers are negative and some positive. You need to find maximal sub-set which the sum of it's elements it's 0 ( zero +- 1).
for ex: {-1,1,1,1,1,3,-2,-7} will have the answer of {1,1,1,1,3,-7}.

just a clarification question:

if you instead had the set {-1,1,1,1,2,3,-2,-7}

is the subset {-1,1,1,1,-2} the answer, or would it be {1,1,2,3,-7}, or both?

Tex23bm

you need the maximum in size therfore {-1,1,1,1,2,3,-7} will do in that case. if you have 2 options with same maximal size anyone will do.

[amoshag]

Do you need it solved or you just share these puzzles? Second question is classic algorithm. First question is about knapsack problem and can be solved using different methods depending on if you need the precise solution.

u say the second problem is a classic algorithm, can you diret me to somwehere i can find it, i looked anywhere, 10x :-)

[olivthill]

The second problem looks like the famous problem of the bridges of Koenigsberg that was tackled by Leonard Euler.

[amoshag]

The second problem looks like the famous problem of the bridges of Koenigsberg that was tackled by Leonard Euler.

Be aware that we'r talking about vertices cover and not edges cover. if you need edges cover by euler theorem the minimal cover will be half the vertices with odd number of outgoing edges (if i'm not wrong... ). Anyway, in this case veertice cover is diffrent story, i know there should be a sollution that involves maxflow mincut algorithm (ford & furkenson)

[RoboTact]

The second problem looks like the famous problem of the bridges of Koenigsberg that was tackled by Leonard Euler.

It's unrelated.

Be aware that we'r talking about vertices cover and not edges cover.

The problem is named minimum path cover.

if you need edges cover by euler theorem the minimal cover will be half the vertices with odd number of outgoing edges (if i'm not wrong... ).

Say, there is a graph with no odd vertex degree. It doesn't mean that minimal edge cover consists on no edges at all, does it?

Anyway, in this case veertice cover is diffrent story, i know there should be a sollution that involves maxflow mincut algorithm (ford & furkenson)

Quite correct.

[amoshag]

It's unrelated.The problem is named minimum path cover. Say, there is a graph with no odd vertex degree. It doesn't mean that minimal edge cover consists on no edges at all, does it? Quite correct.

about edges covers (eulle), well, if there are 0 odd.. so that's a special case where there is an euller circle(that's how it's called?), if there are 2 odd ... so one path will do, 4 odd. 2 path and so on... but, that wasn't the case...

[RoboTact]

about edges covers (eulle), well, if there are 0 odd.. so that's a special case where there is an euller circle(that's how it's called?), if there are 2 odd ... so one path will do, 4 odd. 2 path and so on... but, that wasn't the case...

If you are talking about path cover - correct (not edge cover which is different thing). Anyway, problem is with directed graphs.

[tex23bm]

darn it, Yeah, sorry about that bad question, but i think you answered the question I was attempting to ask. Basically I was trying to ask which you would choose if you had two max subsets of equal size. And the reply I got was that it doesn't matter. Thanks for the clarification, sorry about the mistake in my question.

Tex23bm

[mehdi62b]

1. you are given a set of some integer numbers (some is probebly around 60-70). As integers some of the numbers are negative and some positive. You need to find maximal sub-set which the sum of it's elements it's 0 ( zero +- 1).
for ex: {-1,1,1,1,1,3,-2,-7} will have the answer of {1,1,1,1,3,-7}.

2.you got a DAG (directed acyclic graph) already topolpgical sorted. you want to find the minimum number of distinct paths that will cover all vertices of the graph. for ex: if you got a->b->c->d->e then you got one path that will cover the graph.

well,you should know all such problems can be solved easilly by brute force
for the firts one there are 2^n subsets can be checked..in the second one there are n! possible path could exist should be checked..but well you need more optimized algorithm though!

if there are 2 odd ... so one path will do, 4 odd. 2 path and so on... but, that wasn't the case...

if are 2 odd there is just one eurilian path(every edge should be passed just once) but if there are 4 odd there is no 2 path

First question is about knapsack problem and can be solved using different methods depending on if you need the precise solution.

as far as I know knapsack problem is for possitive numbers.

Undirected Graphs

• G is a hamilton graph if it has a hamilton tour(it's clearly a connected graph)
• every Haiton graph should have a SubGraph which
  
  • for every vertice in the main graph,we must have a vertex in the subgrah which its degree should be 2 so if we can't find any subgraph in respect of the above condittions the graph is not a hamilton graph.
• if for every nonadjacent pair vertices, deg(u)+deg(v) are equal or greater than n (u and v are the nonadjacent vertices and n is the number of vertices) the graph is a hamilton graph so
  
  
  1. if in a graph every vertice has a degree greater or equal than n/2 it is a hamilton graph. (not necessarily inversely)
  2. if the number of edges are equal or greate than [(n-1)(n-2)]/2+2 its a hamilton graph. (not necessarily inversely)
• G is eulerian graph if it has a euilerian tour
• every eulerian graph has
  
  
  1. even degrees
  2. its connected (and inersely)
• in a eulerian path (not tour) for every vertex which is not the beginning ar the ending vertices its degree should be an even number
• if a graph has a eulerian path it doesn't have more than two odd-degree vertices.

EDIT: I declare the dgrees for directed graphs as:

deg(v)=n(input vertices)-n(output vertices)

Directed Graphs

• G is a hamilton graph if it has a hamilton tour(it's clearly a connected graph)
• every Haiton graph should have a SubGraph which
  
  • for every vertice in the main graph,we must have a vertice in the subgrah which its degree should be 0 so if we can't find any subgraph in respect of the above condittions the graph is not a hamilton graph.
• G is eulerian graph if it has a euilerian tour
• every eulerian graph has
  
  
  1. the degrees of every vertex should be 0
  2. its connected (and inersely)
• in a eulerian path (not tour) for every vertex which is not the beginning ar the ending vertices its degree should be 0
• if a graph has a eulerian path it doesn't have more than two odd-degree vertices.

[RoboTact]

And what was the purpose of that message? Of course most of the problems could be solved with force brute enough.
I didn't say it is knapsak problem, I said "it's about knapsack problem", that is could be solved using some knapsack problem algorithm. But stictly speaking, it's equivalent: it's NP-complete problem. I searched a bit in google now, and found that it's also formulated as classic NP-complete problem, named subset sum problem.