AtCoder Beginner Contest 139 Task F Engines

題目大意

給定 $n$ 個二維向量，從中選出若干個，使得它們的和的模最大。

分析

這是一個經典問題，還有一種提法是：

給定 $n$ 個二維向量 $v_1, v_2, \dots, v_n$，求一組系數 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 1$）使得 $\sum_{i = 1}^{n} a_i v_i$ 的模最大。
容易證明：對于最優解，$a_i$ 要么是 1 要么是 0；于是歸約到選擇一個最優子集的問題。

可以證明，最優解滿足下列兩個性質：

• The set of vectors in an optimal solution using a minimal number of vectors must all lie in an open half-plane. 包含向量數目最少的最優解中，所有向量都在一個開的半平面中

如果加上「所選的向量都在一個開的半平面中」這個限制，我們立即可以推論出，若先把所有向量按極角排序，則所選的那些向量必定是其中連續的一段。換言之，

• 對于包含向量數目最少的最優解，其中的向量按極角排序后是連續的一段。The vectors in the optimal solution using a minimal number of vectors are contiguous when ordered according to angle circularly.

References

https://math.stackexchange.com/q/730611/538611

轉載于:https://www.cnblogs.com/Patt/p/11535310.html

總結

以上是生活随笔為你收集整理的【经典问题】maximum subset sum of vectors的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。