# Knapsack-like problem

I need to express an integer $n$ as the sum of integers $x_i$ below some threshold $t$, minimizing the number of $x$s, and maximizing a lower threshold $q$.

$$\min_{\# x} \max_{q} : \sum_i x_i = n \quad q\le x_i\le t$$

For example $n=7$, $t=3$ includes the cases $x=(2,1,1,1,1,1)$ which is too long, $x=(3,3,1)$ with $q=1$ and $x=(3,2,2)$ with $q=2$ which is the optimal solution.

(it's part of an FFT planner: kernels of different sizes can be combined where performance degrades for kernels larger than $t$, but using smaller kernels isn't optimal either, $3,3,1$ performs worse because of $1$ than $3,2,2$ would, for example, which is why $q$ should be maximized.)

Minimizing the number is trivial: $\#x = \lceil n/t\rceil$, so the problem becomes

$$\max_q : \sum_i x_i = n \quad q \le x_i \le t$$

I can't think of a way to maximize $q$ that isn't completely naive. Not sure what keywords I could use to look for a solution to this…

-

It is not clear whether you must have $x_i \lt t$ or is $x_i=t$ acceptable. I will assume $x_i=t$ is acceptable, but the changes for strictly less are easy-just set $t'=t-1$ and follow along.
You are right, the number of terms is $\#x= \lceil n/t\rceil$. Then if all the $x_i=t$ the sum will be $t\#x$, so you need to remove $r=t\#x-n$. To maximize $q$ you should spread this as evenly as possible, so you remove $\lfloor \frac r{\#x} \rfloor$ from all of them, which leaves you $r-\#x\lfloor \frac r{\#x} \rfloor$ to go and you can remove one more from each of that many $x_i$. It may sound naive, but it works. The result is that you have $$\#x= \lceil n/t\rceil\\r=t\#x-n$$
Leading to the partition $$\\r-\#x\lfloor \frac r{\#x} \rfloor \text { copies of }t-\lfloor \frac r{\#x} \rfloor-1\\ \#x-r+\#x\lfloor \frac r{\#x} \rfloor \text { copies of }t-\lfloor \frac r{\#x} \rfloor$$