## 5 Properties Analysis of the Functions \(\varphi_{m}^{s}\)
### Single-Resource-Block Maritime User Allocation
In addition, the execution time is limited by both the size of the polynomial input and \(1/\varepsilon\). Supposing that \(P\
eq NP\), the DP-FPTA algorithm is the best compromise solution to the NP-hard optimization problem. The algorithm ensures the performance of WAR while reducing the computational difficulty [34]. As shown in Algorithm 7, the DP-FPTA algorithm is based on a combination of profit-based dynamic programming and an approximate optimal scheme. Scaling profit generally contributes to the simplification of the items calculated in the knapsack problem. We first give an estimate \(F*\) of the optimal value of the \(W_{MKCP}\) problem; the estimated value satisfies the requirements of the condition \(F*\geq W_{MKCP}*\geq\frac{F\varepsilon}{4}\)[34]. To further simplify the workload, we focus only on subset \(J_{s}\) of the items for each category rather than calculating the profit value \(pro_{j}^{s}\) of the total items for \(S\) categories. \[J_{s}=\left\{l\leq J,j\leq\frac{4S}{\varepsilon}-1,pro_{l-1}^{s}<j\frac{ \varepsilon F*}{4S}\leq pro_{l}^{s}\right\}. \tag{66}\]

The discrete terms of the DP-FPTA scheme can be expressed as \(j\in\left\{1,2,\ldots,\frac{4S}{\varepsilon}\right\}\) to transform the continuous profit space into discrete values for every interval \(\left[(j-1)\cdot\frac{\varepsilon F*}{4S},j\cdot\frac{\varepsilon F*}{4S}\right]\). Subsequently, we introduce a multi-key binary search to obtain subset \(J_{s}\) on each resourceblock [35]. Finally, as shown in lines 11-14 of Algorithm 7, we adopt profit-based DP to obtain the optimal solution for resource allocation. Let \(Q\) denote a DP array for the smallest weight of the subproblem composed of \(S\) categories (resource blocks), the problem of MCKP be limited to the first \(s\) categories, and \(Q\)(\(s\),\(q\)) denote the minimum power budget required to achieve a WAR of \(q\)-\(\varepsilon F^{*}/4S\). After initializing \(Q\)[0,0] = 0, \(Q\)[0,\(q\)] = +\(\infty\) and letting \(q=0,1,\ldots,\left\lfloor\frac{4S}{\varepsilon}\right\rfloor\), the recursive relationship can be expressed as

\[[s,q]=\underset{j\in I_{s}}{min}\left\{ \begin{array}{c}Q\Big{[}s-1,q-\left \lfloor\frac{4 pr^{s}_{j}S}{\varepsilon F^{*}}\right\rfloor\Big{]}+wei^{s}_{j },\frac{q+F*}{4S}\geq proj^{s}_{j}\\ +\infty,\,\text{Otherwise}\end{array} \right., \tag{67}\]

where \(|J_{s}|=min\left\{\frac{4S}{\varepsilon},I\right\}\). Furthermore, the gap between the DP-FPTA optimal solution and the MCKP-DP optimum \(W_{MCKP}*\) is, at most, \(\varepsilon\cdot W_{MCKP}*\). The calculative complexity of DP-FTPA is \(O(SAT^{2}+\min\{(log_{2})\}\frac{S^{2}AT}{\varepsilon+\frac{S^{2}}{\varepsilon ^{2}}},JSAT+J^{2}S)\). ```
1:Function DP-FPTA \((\boldsymbol{\alpha},T,B_{S},G^{s}_{t}(t\in T),\sigma^{s}_{t}(t\in T),A,p^{s} _{max,s}\)
2:Calculate an estimated value \(F*\) of \(W_{MCKP}*\), \(F*\geq W_{MCKP}*\geq\frac{F*}{4}\)
3:For\(s\in S\)do
4:K=\(\varepsilon F*/S\)
5:For\(j\in I_{s}\)do
6:While\(proj^{s}_{j+1}-proj^{s}_{j}>K\)do
7:Obtain \(proj^{s}_{j},wei^{s}_{j}\) through multi-key binary search method
8:Endwhile
9:Endfor
10:Endfor
11:For\(s\in S\)do
12:For\(q\in\left[\boldsymbol{0},\boldsymbol{1},\ldots,\left\lfloor\frac{4S}{ \varepsilon}\right\rfloor\right]\)do
13:\(Q[s,q]=min\left\{Q\Big{[}s-1,q-\left\lfloor\frac{4 pr^{s}_{j}S}{\varepsilon F ^{*}}\right\rfloor\Big{]}+we^{s}_{j}\right\}\)
14:Endfor
15:Endfor
16:Return DP-FPTA allocation by means of the profits-based dynamic programming [28]
17:EndFunction DP-FPTA
```

**Algorithm 7** Fully polynomial time approximation program based on dynamic programming (DP-FPTA)

Remark: In [34], it is pointed out that in a very technical sense, the FPTA scheme is the best one can expect for an NP-hard optimization problem, assuming that \(P\
eq NP\). The design of almost all the FPTA and PTA schemes is based on the idea of trading accuracy for running time. Inspired by the idea of an approximate algorithm, we can deal with the NP-hard problem in the following three ways.