Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given $n$ sorted items, as a following set $I$:

$\{i_1, i_2, ... i_n\}, i \in \mathbb{R} $.

We can calculate $\sum_{a=1}^{n}i_a = S$. Now, a target $T$ is provided and the challenge is to find a (sorted) subset $R$ with elements $\{ r_1, r_2, r_3 ... r_m\}$ (and hence cardinality of it as $m$), such that:

$\sum_{x=1}^{m}r_x = \frac{T}{S}$

I am looking for a formula. Does it exist?

I took a look at another related question: Given a collection of items, how many ordered subsets can I make?. But I am looking for cardinality of one subset with the sum, I need.

share|improve this question
4  
This is the subset sum problem. You might start at en.wikipedia.org/wiki/Subset_sum_problem or search the web –  Ross Millikan May 4 '12 at 1:59
    
@Ross +1. And thanks for the pointer. –  Guru May 4 '12 at 2:54
    
Glad to help. If you don't know the name a problem has been studied under, it can be hard to find information on it. –  Ross Millikan May 4 '12 at 3:03
    
What is $\; r_x$? –  copper.hat May 4 '12 at 7:15
    
@copper.hat, $r_x$ would be elements in set $R$. Sorry, that is not mentioned clearly in the question. –  Guru May 4 '12 at 19:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.