挑数字

123456789

从自然数中挑选K个数（可以重复选取）组成一个数组，使得其中不超过3个元素之和可以连续取到1~N，现已知N。求数组中元素个数最少且最大值最小的一个。

比如N=10，（1,2， 4 ，4），（1,2,2,6）和（1,2,3,7）都满足个数最少，但（1,2，4,4中最大值为4）。所以结果是（1,2,4,4）。
1=1
2=2
1+2=3
4=4
1+4=5
2+4=6
1+2+4=7
4+4=8
1+4+4=9
2+4+4=10

现在N=10000，求该数组。

ocideeweguy

看看我的数据正确与否：
1        {1}
2        {1,1}
3        {1,2}
4        {1,1,2}
5        {1,2,2}
6        {1,2,3}
7        {1,2,4}
8        {1,2,3,3}
9        {1,2,3,4}
10        {1,2,4,4}
11        {1,2,4,5}
12        {1,2,4,6}
13        {1,2,4,7}
14        {1,2,4,8}
15        {1,2,3,6,6}
16        {1,2,3,6,7}
17        {1,2,3,6,8}
18        {1,2,3,6,9}
19        {1,2,3,6,10}
20        {1,2,3,6,11}
21        {1,2,3,6,12}
22        {1,2,4,7,13}
23        {1,2,4,7,14}
24        {1,2,3,6,10,11}
25        {1,2,3,6,10,12}
26        {1,2,3,7,11,12}
27        {1,2,3,7,11,13}
28        {1,2,3,7,11,14}
29        {1,2,4,8,13,14}
30        {1,2,3,6,10,17}
31        {1,2,3,6,10,18}
32        {1,2,3,6,10,19}
33        {1,2,3,6,10,20}

azanuvahejih

怎么算出来的？

akomosuse

aimisiyou 发表于 2023-12-4 13:23
怎么算出来的？

1. f[n_]:=Module[{x=Prepend[1]/@Union[Sort/@Tuples[Range[n/2+5],Floor[Log2[n]]]]},y=Select[x,Complement[Range@n,Union[Total/@(Subsets[#,3])]]=={}&];First@SortBy[y,Last]];Table[{n,f[n]},{n,20}]

复制代码

akomosuse

未返回结果的项数加1即可

{{1,{1}},{2,{1,1}},{3,{1,2}},{4,{1,1,2}},{5,{1,2,2}},{6,{1,2,3}},{7,{1,2,4}},{8,{1,2,3,3}},{9,{1,2,3,4}},{10,{1,2,4,4}},{11,{1,2,4,5}},{12,{1,2,4,6}},{13,{1,2,4,7}},{14,{1,2,4,8}},{15,First[{}]},{16,{1,2,3,6,7}},{17,{1,2,3,6,8}},{18,{1,2,3,6,9}},{19,{1,2,3,6,10}},{20,{1,2,3,6,11}}}

BristSes

不知道是否最优解，但在n>15时， {1,2,3,6}，{1,2,3,7}， {1,2,4,7}, { {1,2,4,8}必出。