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?
Printable View
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.Quote:
Originally Posted by HappyNerd
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.
Not sure about a lower complexity algorithm. This problem is a variation of the subset sum problem, which is NP-complete.Quote:
Originally Posted by nuzzle
Regards,
Zachm
that's actually very helpful, thank you!Quote:
Originally Posted by nuzzle
I'll read about it. thanks!Quote:
Originally Posted by Zachm
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?
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).Quote:
Originally Posted by HappyNerd