help with recursion

[adato]

hello.

I have an array of int and a number
I need to build a recursion that print all the sub groups that if I summarize them, the summery is smaller then the number .
if some one can help me and write me the code I will be greatful.

Thank you.

[Sick0Fant]

When you talk of subgroups, are you speaking of the Algebraic structure? Or did you mean subsets? More info, please.

[sanctus]

hello.

I have an array of int and a number
I need to build a recursion that print all the sub groups that if I summarize them, the summery is smaller then the number .
if some one can help me and write me the code I will be greatful.

Thank you.

How are the subgroup defined? Any possible combination of the elements of the int array or something else?

Why don't you post what you have come up with?

[adato]

this is my problem

A thief has a knapsack of a certain capacity. He looks around and sees different items of different weights and values. He would like the items he chooses for his knapsack to have the greatest value possible yet still fit in his knapsack. The problem is called the 0-1 Knapsack Problem because the thief can either take (1) or leave (0) each item.

out put the best value in minimum weight and an array of indactors that indicate by 1 or 0 which items the thief take

[sicarie]

So what do you have on this so far?

[JosAH]

this is my problem

A thief has a knapsack of a certain capacity. He looks around and sees different items of different weights and values. He would like the items he chooses for his knapsack to have the greatest value possible yet still fit in his knapsack. The problem is called the 0-1 Knapsack Problem because the thief can either take (1) or leave (0) each item.

out put the best value in minimum weight and an array of indactors that indicate by 1 or 0 which items the thief take

This question is entirely different from yor first question. Now you want this:

- max(sum(a_i*w_i) <= W
- w.r.t. a_i in [0,1] integer

Your first question completely skipped the maximization constraint. You have to
be accurate when you formulate a problem and ask a question about it.

kind regards,

Jos

[adato]

sorry
I have tried to dived the problem to smaller problems
i though it will be easy for you.

[JosAH]

sorry
I have tried to dived the problem to smaller problems
i though it will be easy for you.

No it isn't; maximixing that a_i*w_i essentially demands another algorithm than
just finding feasible solutions. For the 0/1 Knapsack problem think along the
following (recursive) line:

Start with k == n.

- set up a sequence w_0, w_1, ... w_k
- the knapsack has volume W
- only the elements 0 ... k are allowed to be in the knapsack.

solve the two subproblems (this is the recursive step)

- w_0, w_1 ... w_k-1
- the knapsack has volume W-w_k
- ony elements 0 ... k-1 are allowed

and

- w_0, w_1 ... w_k-1
- the knapsack has volume W
- only element 0 ... k-1 are allowed

The value k starts at k == n.

for the second (locally optimal!) solution see if w_k still fits in the knapsack.

Take the better of the two solutions. The recursion ends when k < 0.

kind regards,

Jos