关于解决背包问题(n+3)*(2^(n/2))复杂度相关的问题

showjim

以前知道背包问题非DP方法是将n个数平均分成2份，分别求全排列并排序，然后分别从两端往中间扫描，总复杂度为(n+3)*(2^(n/2))。如n=50时，结果为1778384896。 我发现，把n个数分成3个部分，效率更高。比如50个数分为v6+v44，v44按照上面的方法平均分成2份分别求全排列并排序，根据v6中的每一个数对v44做背包运算。 下面是当6>=n>=60的复杂度列表：6 : 72 - 44(2,2) = 28 %= 1.63636363636364 7 : 128 - 64(3,2) = 64 %= 2 8 : 176 - 100(2,3) = 76 %= 1.76 9 : 304 - 136(3,3) = 168 %= 2.23529411764706 10 : 416 - 208(4,3) = 208 %= 2 11 : 704 - 296(3,4) = 408 %= 2.37837837837838 12 : 960 - 432(4,4) = 528 %= 2.22222222222222 13 : 1600 - 648(3,5) = 952 %= 2.46913580246914 14 : 2176 - 912(4,5) = 1264 %= 2.3859649122807 15 : 3584 - 1416(3,6) = 2168 %= 2.53107344632768 16 : 4864 - 1936(4,6) = 2928 %= 2.51239669421488 17 : 7936 - 2976(5,6) = 4960 %= 2.66666666666667 18 : 10752 - 4112(4,7) = 6640 %= 2.6147859922179 19 : 17408 - 6176(5,7) = 11232 %= 2.81865284974093 20 : 23552 - 8720(4,8) = 14832 %= 2.70091743119266 21 : 37888 - 12832(5,8) = 25056 %= 2.95261845386534 22 : 51200 - 18448(4,9) = 32752 %= 2.77536860364267 23 : 81920 - 26656(5,9) = 55264 %= 3.07322929171669 24 : 110592 - 38928(4,10) = 71664 %= 2.84093711467324 25 : 176128 - 55328(5,10) = 120800 %= 3.18334297281666 26 : 237568 - 81936(4,11) = 155632 %= 2.89943370435462 27 : 376832 - 114720(5,11) = 262112 %= 3.28479776847978 28 : 507904 - 172048(4,12) = 335856 %= 2.95210638891472 29 : 802816 - 237600(5,12) = 565216 %= 3.37885521885522 30 : 1081344 - 360464(4,13) = 720880 %= 2.99986683829731 31 : 1703936 - 491552(5,13) = 1212384 %= 3.46644098691491 32 : 2293760 - 753680(4,14) = 1540080 %= 3.04341365035559 33 : 3604480 - 1015840(5,14) = 2588640 %= 3.54827531894787 34 : 4849664 - 1540160(6,14) = 3309504 %= 3.1488053189279 35 : 7602176 - 2097184(5,15) = 5504992 %= 3.62494468773365 36 : 10223616 - 3145792(6,15) = 7077824 %= 3.24993387992595 37 : 15990784 - 4325408(5,16) = 11665376 %= 3.69694234624803 38 : 21495808 - 6422592(6,16) = 15073216 %= 3.3469054238538 39 : 33554432 - 8912928(5,17) = 24641504 %= 3.76469236596548 40 : 45088768 - 13107264(6,17) = 31981504 %= 3.43998320320702 41 : 70254592 - 18350112(5,18) = 51904480 %= 3.82856475208435 42 : 94371840 - 26738752(6,18) = 67633088 %= 3.52940331695361 43 : 146800640 - 37748768(5,19) = 109051872 %= 3.88888559223973 44 : 197132288 - 54526016(6,19) = 142606272 %= 3.61538037182104 45 : 306184192 - 77594656(5,20) = 228589536 %= 3.94594431863968 46 : 411041792 - 111149120(6,20) = 299892672 %= 3.69811107816238 47 : 637534208 - 159383584(5,21) = 478150624 %= 3.999999196906 48 : 855638016 - 226492480(6,21) = 629145536 %= 3.77777671029078 49 : 1325400064 - 327155744(5,22) = 998244320 %= 4.05128165501505 50 : 1778384896 - 461373504(6,22) = 1317011392 %= 3.85454491985738 51 : 2751463424 - 671088672(5,23) = 2080374752 %= 4.09999980449677 52 : 3690987520 - 939524160(6,23) = 2751463360 %= 3.92857116095876 53 : 5704253440 - 1375731744(5,24) = 4328521696 %= 4.14634136696929 54 : 7650410496 - 1912602688(6,24) = 5737807808 %= 3.99999986615098 55 : 11811160064 - 2818572320(5,25) = 8992587744 %= 4.1904761429006 56 : 15837691904 - 3892314176(6,25) = 11945377728 %= 4.06896545033676 57 : 24427626496 - 5771362336(5,26) = 18656264160 %= 4.23255811606697 58 : 32749125632 - 7918846016(6,26) = 24830279616 %= 4.13559318691518 59 : 50465865728 - 11811160096(5,27) = 38654705632 %= 4.27272726115116 60 : 67645734912 - 16106127424(6,27) = 51539607488 %= 4.1999999833107 很明显，对于6x+i的序列的复杂度倍率是递增并收敛的。 我想问的是，这个6x+i的复杂度倍率序列会一直递增吗？ 如果是一直递增，因为是收敛的会不会存在极限值，那么极限值n是多少？ 如果不一直递增，我想知道的是倍率小于1的n的最小值是多少？

showjim

从概率上分析，当n=50时，v6应该选择最小的6个数，使得全排列序列左较小。 比如v6的全排列为{a-10,a-9,a-8,a-6,a-5,a-4,a-3,a-2,a-1,a}时，如果a对于v44的背包最优下限为a-7时，那么{a-6,a-5,a-4,a-3,a-2,a-1,a}对于v44背包的最优下限就不必扫描了，必定也为a-7。 也就是v6全排列的排序后的数值越接近越好。