The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A334211 a(n) = 1 + a(n-1)*(A007018(n-1) + 1), with a(0) = 1. 0
 1, 3, 10, 71, 3054, 5518579, 18009568007498, 191802924939285448393150887, 21754999921504126977590785836876485101156736372842942 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,2 COMMENTS The denominator for the infinum of the ratio of the optimal value for the objective functions of the integer knapsack problem with n+1 types of items with the additional restriction that only one type of items is allowed to include in the solution and without it. [Sentence not clear, needs editing. - N. J. A. Sloane, Mar 07 2021] The numerator is A007018(n+1). The sequence a(n)/A007018(n) decreases monotonically and tends to 0.591355492056890... The infinum for a(n)/A007018(n) is achieved on the problem maximize Sum_{j=1..n} x_j/A007018(j-1), subject to Sum_{j=1..n} x_j/(A007018(j-1)+mu_n) <= 1, where 0 <= mu_n < 1 and Sum_{j=1..n} 1/(A007018(j-1) + mu_n) = 1. In particular, mu_1 = 1, mu_2 = (sqrt(5)-1)/2 =~ 0.61803, mu_3 =~ 0.93923, mu_4 =~ 0.99855. The optimal solution vector to this problem is (1,1,...,1) and the optimal solution value is a(n+1)/A007018(n+1), whereas the approximate solution vectors are (1,0,0,...,0), (0,A007018(1),0,...,0), (0,0,A007018(2),...,0), ..., (0,0,0,...,A007018(n-1)) and the corresponding value of the objective function is 1. LINKS A. Yu. Chirkov, D. V. Gribanov and N. Yu. Zolotykh, On the Proximity of the Optimal Values of the Multi-Dimensional Knapsack Problem with and without the Cardinality Constraint, arXiv:2004.08589 [math.OC], 2020. A. Yu. Chirkov and V. N. Shevchenko, On the approximation of an optimal solution of the integer knapsack problem by optimal solutions of the integer knapsack problem with a restriction on the cardinality, Diskretn. Anal. Issled. Oper., Ser. 2, 13 (2) (2006), 56-73. R. Kohli, and R. Krishnamurti, A total-value greedy heuristic for the integer knapsack problem, Operations Research Letters, 12 (1992), 65-71. CROSSREFS Cf. A007018. Sequence in context: A208999 A181075 A136507 * A337949 A086846 A277614 Adjacent sequences:  A334208 A334209 A334210 * A334212 A334213 A334214 KEYWORD nonn AUTHOR Nikolai Zolotykh, Apr 18 2020 EXTENSIONS Definition has been replaced by the explicit recurrence in terms of A007018. - N. J. A. Sloane, Sep 14 2020 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 18 19:04 EDT 2021. Contains 345120 sequences. (Running on oeis4.)