An approach to the partition problem

Правка en2, от phuthuynhochienthan, 2023-08-03 11:52:12

I have found a problem like this: given $$$n$$$ kind of cakes with amounts $$$a_1, a_2, ..., a_n$$$ (i.e. 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. 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

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

I have two questions: is this problem new 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)