Problem seems to be easy but i just cant figue it out!

[HappyNerd]

Problem:
Read 10 integers from the user and calculate the maximum sum that can be created by any of the numbers, and that the sum will not exceed 100.

Now, i just can't figure it out :/
any help guys?

[nuzzle]

Problem:
Read 10 integers from the user and calculate the maximum sum that can be created by any of the numbers, and that the sum will not exceed 100.

Now, i just can't figure it out :/
any help guys?

Viewed as a combinatorial problem you can generate all subsets of 10 numbers and check which subset sum is closest to (but not above) 100.

One easy way to generate the subsets is to simply loop an integer variable from 1 to (2^10) - 1. If you look at the bit sequences of this integer it will go like,

0000000001
0000000010
0000000011
...
1111111111

Each bit sequence represents a subset and each bit position represents one of the 10 numbers. If a bit is set the number corresponding to this position is included in the subset.

I'm sure there's a lower complexity algorithm available but since there are just 10 numbers the above exhaustive approach is still feasible.

[Zachm]

I'm sure there's a lower complexity algorithm available but since there are just 10 numbers the above exhaustive approach is still feasible.

Not sure about a lower complexity algorithm. This problem is a variation of the subset sum (http://en.wikipedia.org/wiki/Subset_sum_problem) problem, which is NP-complete.

Regards,
Zachm

[HappyNerd]

Viewed as a combinatorial problem you can generate all subsets of 10 numbers and check which subset sum is closest to (but not above) 100.

One easy way to generate the subsets is to simply loop an integer variable from 1 to (2^10) - 1. If you look at the bit sequences of this integer it will go like,

0000000001
0000000010
0000000011
...
1111111111

Each bit sequence represents a subset and each bit position represents one of the 10 numbers. If a bit is set the number corresponding to this position is included in the subset.

I'm sure there's a lower complexity algorithm available but since there are just 10 numbers the above exhaustive approach is still feasible.

that's actually very helpful, thank you!

Not sure about a lower complexity algorithm. This problem is a variation of the subset sum (http://en.wikipedia.org/wiki/Subset_sum_problem) problem, which is NP-complete.

Regards,
Zachm

I'll read about it. thanks!

I got another question:
Is there an efficient algorithm to find all of the permutations of a certain number.
for example the user types:
9611
and the program prints:
1169
1196
1619
1691
...
6911
9611

any help guys?

[nuzzle]

that's actually very helpful


Note that as an alternative, the subsets can be generated by the use of 10 nested for-loops each looping from 0 to 1. It may be more convenient because there's no need to extract bits from integers. The 10 loop variables will hold the bits (be either 0 or 1).