Input: a set of 2D vectors $S=\{v_1,v_2,\dots,v_n\mid v_i\in \mathbb{Z}^2 \}$  Question: name $P=\{\sum_{v_i\in S'}v_i\mid S'\subseteq S \}$   for all subsets of $S$ (obviously $|P|=O(2^n)$). In  words, $P$ is the set of all possible vectors we can form by adding  vectors from $S$.  What is the length of the longest vector in $P$?An idea:(An easy observation is that if all $v_i\in S$ are in one orthant (or quadrant?) we just have to add them. If the vectors are in on hyperplane this is not true.)Start from an arbitrary vector $v_1\in S$, get the next one $v_2$ (either left or right) and add $V=v_1+v_2$. Generally, at each step $V=V+v_i$. Continue this while $|V|$ is increasing. At some time we find $v_j$ such that $V=V+v_j$ shortens. Set $V=V-v_1+v_j$ and continue. The idea is to maintain a window where we add all the vectors inside. If the next vector (the one side of the window) does not add, remove the first one (the other side of hte window).  I know I am not clear enough but hope you get the idea.Is this correct? Am not sure...An other ideas/approaches? (This, of course, can be generalized to any dimension $k$. I mentioned the 2D case because it is easy to visualize.)I am looking for algorithms with polynomial time on $n=|S|$.Related problem: lattice problems.Let set $S$ be the basis of the lattice $L$. Then $L$ is defined as$$L(S)=\{\sum_{i=1}^{n}a_i v_i \mid v_i\in S, a_i\in\mathbb{Z}\} $$Our set $P$ is a special case if, instead of $a_i\in\mathbb{Z}$ we let $a_i\in \{0,1\}$.
Given a set of 2D vectors, find the furthest reachable point
algorithms;optimization