Consider some tuple $x = (x_1, ..., x_k) \in \mathbb{N}^k$ of $k$ non-negative integers such that $x_1 > x_1 > ... > x_k$ and suppose that $A \subset \mathbb{N}^k$ is such that there exists a fixed $n \in \mathbb{N}$ with the property that $a_1 + ... +a_k = n$ for all $a \in A$.
Is there an efficient method/algorithm to find an $a \in A$ which maximizes the quantity $\langle x, a \rangle = x_1a_1 + ... + x_ka_k$?
EDIT: So after reading Robert Israel's answer and comments, it seems that the problem is not very feasible without additional constraints. Here are two additional assumptions I would be willing to accept. The first concerns $x$.
- Let's assume that $x$ is of the form $x = (x_1, x_1 - 1, x_1 - 2, ..., x_1 - (k-1))$
The second concerns the set $A$, although I'm not sure it will be of much use. Define $A(n) = \{a \in \mathbb{N}^k: a_1 + ... + a_k = n\}$. The point of the question is to design an algorithm which enumerates the members of $A(n)$ as $a_1, ..., a_m$ in such a way that $\langle x, a_i \rangle \geq \langle x, a_j \rangle$ if $i < j$. The idea then is to
Find an element $a$ which maximizes $\langle x, a \rangle$
Write this element down and remove if from the set
Repeat steps 1 and 2 until all the elements have been removed
So I guess what this tell us about $A$ in the original question is that it is not completely arbitrary, but chosen in such a way that if $a \in A$ and $\langle x, a \rangle = l$ then $A$ contains all elements $b \in A(n)$ such that $\langle x, b \rangle \le l$.
As has been pointed out, in some cases the maximizing element is obvious. For example, at the first step, the maximizing element will always be $(n, 0, ..., 0)$.