An approach to the partition problem
Разница между en2 и en3, 295 символ(ов) изменены
I have found an interesting problem like this: given_there are $n$ kind of cakes with amounts $a_1, a_2, ..., a_n$ (i.e.and for $1 \le i \le n$, there are $a_i$ cakes of the $i-$th kind for $1 \le i \le n$). We need to take out as much as $k-$ tuples of distinct cakes. WSo with the given value of $k \ge 1$ and array $a_1,a_2,...,a_n$, what is the maximum number of tuples can we get?


~~~~~
_↵

For example: we have $4$ kinds of cake as $(A,B,C,D)$ with amounts: $a[4] = 
\{(20,30,40,50 \})$ and $k=3$. We can get at most $45$ tuples as: $5$ tuples $(A,B,C)$ and $15$ tuples $(A,C,D)$ and $25$ tuples $(B,C,D)$.
~~~~~↵

 

I came up with this idea to solve as follow: ↵

<spoiler summary="Spoiler">↵
Denote $d$ as the number of $k-$tuple we can get then 
it is easy to check that $d \gle \dfrac{s}{k}$ with $s$ is the sum of all amounts. Then we can make this estimation stronger by the remark: the number of used cakes of each kind is also upper bounded by $\frac{s}{k}$, we iteratively update all numbers $a_i$ in the given array by this value., i.e $a_i = $ minimum of $a_i$ and $\dfrac{s}{k}.$ So we have the new array with new sum $s'$ and a new upper bound $\d \le \dfrac{s'}{k}$. We do this until there is no update and then get the answer.↵
</spoiler>↵

By this idea, for the test case as: $a[5] = 
\{(1,2,3,1000,1000\})$ and $k=4$, I got the answer is $3$ after some iterations. And by checking with some other tricky test cases, I'm pretty sure this idea is true.↵

I have two questions: 
i_Is this problem new a? And how to find a proof for this approach?_ Thanks for your help. 

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский phuthuynhochienthan 2023-08-03 12:06:19 295 Tiny change: 'ch as $k-$tuples of ' -> 'ch as $k-$ tuples of ' (published)
en2 Английский phuthuynhochienthan 2023-08-03 11:52:12 92
en1 Английский phuthuynhochienthan 2023-08-03 11:49:19 1379 Initial revision (saved to drafts)