Unmanned aerial vehicle (UAV)-aided Wireless Rechargeable Sensor Network (WRSN) is a promising application in providing sustainable power supply to the rechargeable sensor nodes (SNs). Constructing a trajectory for the UAV to traverse all SNs with the cheapest cost is an important issue in UAV-aided WRSN. Although some exact algorithms and heuristic methods have been proposed, they cannot achieve a superb result for the large-scale scene within the tolerable time. In this paper, we study the UAV`s trajectory optimization problem from a novel viewpoint that the designed trajectory should maximize the UAV's energy utilization efficiency. The maximum UAV's energy utilization efficiency problem is decomposed as integer programming and non-convex optimization problems. For the problem that UAV`s charging position is fixed, we have speeded the algorithm's performance by limiting the search direction, the initial search position, and the search space. In the other case, where the power transfer efficiency is unchangeable within a certain distance, a polynomial-time randomized approximation scheme (PRAS) is presented to find the approximate minimum number of hovering locations. We have presented TPA-FCP and TPA-ERC to solve the above problems, respectively. The numerical results verify that our proposed algorithms effectively reduce the length of optimal trajectory and the time complexity. Besides, the energy carried by the UAV for the specified task is predictable, which provides valuable information for arranging the UAV's flight task.