Background:
This is a problem that I randomly brainfartted and I found it quite interesting, I cannot think about a feasible solution yet.
Body:
Problem Definition
I am trying to find a sequence S such that for each number i from 1 to n, a score f(i) is calculated and minimized using the following formula:
f(i) = a * |S| + (1-a) * N(S, i)
where:
- |S| is the length of the sequence S.
- N(S, i) is the minimum number of elements from S required to sum up to the target i. Elements in the sequence S can be used repeatedly.
- a is a parameter between 0 and 1 that balances the contribution of |S| and N(S, i) to the score.
The objective is to find such a sequence S that yields the lowest possible score f(i) for every i from 1 to n.
What I’ve Tried
I initially attempted a brute-force approach to generate possible sequences and evaluate them, but this method is computationally expensive and unfeasible for larger numbers (e.g., n = 20 and beyond).
Questions
- Are there more efficient algorithms or methods to approach this problem, possibly using dynamic programming or other optimization techniques? Is there a known problem or mathematical framework that resembles this problem structure, which could guide the development of a solution? Do you guys have any idea how to solve this problem?
Ideas
I thought about using random approximation to approximate the solution but I cannot execute the idea.
Observations:
-
Idk how to proof, but the sequence of {1,2,3,…,N} can form any numbers between 1 and (1+N)N/2. Therefore, if a=1, the optimal sequence should be {1,2,3,…,x} where argminx (1+x)x/2 >= target
-
If a=0, (1-a)=1, N(S,i) is always 1 because we can form a sequence {1,2,3,…,T}, such that we can just use a single number itself to represent any number below the target
-
Based on observation 1 and observation 2, I guess the optimal sequence should be between the combination of {1,2,…x} to {1,2,…,T}, and there will be total of T-x+1 of such iterations.