Algorithm 1 Identify the dominance relations among the into.Then similarly we can recursively calculate the optimal items solution step by step.Hence the compute complexity of the 1:Put all 2kpt items into the search space S. dynamic programming is O(m·M·K·于) 2:Sort the items in decreasing order of reduced energy Ei rename the items as i(1 <is 2opt)according to the 5.4 Greedy Approximation Algorithm rank. We already know that the dynamic programming based al- 3:Sort the items in increasing order of required number of gorithm is able to solve the problem in a pseudo-polynomial storage Nil. time.However,as the number of storages,K,increases to 4fori∈[1,2 Kopt]and i∈Sdo a large value,the compute complexity is still fairly large 5: for j [i+1,2op]and jeS do Therefore,a greedy approximation algorithm is essential to 6: ifN[间<N[i]then be proposed to solve the above problem in a more time- 7 Remove item j from the item set S,S=S-j efficient approach. 8: end if end for Consider the situation with limited number of storages,it 10:end for can be understood that conventionally the storage is a scarcer resource than the other issues such as the space.Here we use the notion sack to denote the fan-shaped partition.Algo Suppose after identifying the dominance relation,the size rithm 2 illustrates the greedy approximation algorithm.In of the search space is reduced from 2 to M.Then we this algorithm,for any sack-item pair(i,j)(1≤i≤m,1≤ can utilize dynamic programming to solve the unbounded j<M),we first sort the pairs in decreasing order of re- two-dimensional knapsack problem. duced energy per storage unit,i.e.,;then among the N If the deployment area is a circular area with regular shape pairs with equivalent vale ofwe further sort them then according to the problem formulation in (7),we main- in decreasing order of reduced energy per degree unit,i.e. tain a tableF]to denote the maximum reduced energy Elillil.As the degree 0 is equivalent for all pairs,thus the cost,which can be attained with the following constraints: pairs are actually sorted according to the value of Elilj After that,we proceed to insert the corresponding items It uses items up to the jth kind; into the sacks.Among all sack-item pairs,we start from The required number of storages is less than or equal the sack-item pair (i,j)which ranks first in the sorted pairs. to k; putting as many copies as possible of the item j into the sack i until there is not enough space for the item j in sack The required number of items is less than or equal to i.Then we continue to insert the copies of the items into 1. corresponding sacks according to the ranking of the sack- item pairs,until there is no longer space for any kind of the item in the corresponding sack for more. Hence we can define f]k recursively as follows: FIO][k][4]=0 Algorithm 2 Greedy Approximation Algorithm F时=maxos,≤min帝H/ (10) 1:Calculate Elij and Nj for all sack-item pairs (i,j). (f=F[i-[k-x财N[]-x·0+x,·E[] 2:Sort all the sack-item pairs (i,j)in decreasing order of The above formulation shows that whenj=0.no items can be used,the reduced energy cost is 0;otherwise,according 3:Among the items with equivalent value of,further to the value of Flj-1][k-x;N[illll-;0],we can sort all the sack-item pairs (i,j)in decreasing order of calculate the value of Filk]l]by obtaining the maximum E[[]. value of F[i-1][k-x,·N[j吧-E·)+x·E[through 4:Push the ranked sack-item pairs (i,j)into a queue Q. enumerating all possible values of i. 5:k=K,l:=号(i∈[1，m) 6:while >0 andli>0 for at least one sack i do Therefore,if we maintain a three-dimensional table Filk] 7: Pop one sack-item pair (i,j)from Q. of size M×Nx言，we can calculate each value of F[lkjg 8: if li>0 then recursively according to the formulation (10).then finally Put ri.j copies of item j into sack i,here ij= we can obtain the value of f*=FM,which is min{,间 the maximum reduced energy cost.By tracing back each 10: end if j(0<j<M)used to achieve f",we can obtain the opti- 11: k=k-x,·N[,li=l2-x,·0(i∈[1，m) mal parameters for the optimal storage placement.Since the 12:end while computation of f involves examining M items,and there are Kx values of each Fj to calculate by using items The above greedy approximation algorithm has the following up to j,the compute complexity of the dynamic program- properties in term of performance,as shown in Theorem 3. ming is O(M.K·) If the deployment area is in irregular shape,then according THEOREM 3.Assume Emar is the marimum value of items to the problem formulation in (8),we can add an additional that fit into the sack in the unbounded knapsack problem, dimension to denote which partition the current item is put then with limited number of storages,the greedy approrima-Algorithm 1 Identify the dominance relations among the items 1: Put all 2kopt items into the search space S. 2: Sort the items in decreasing order of reduced energy E[i], rename the items as i(1 ≤ i ≤ 2 kopt ) according to the rank. 3: Sort the items in increasing order of required number of storage N[i]. 4: for i ∈ [1, 2 kopt ] and i ∈ S do 5: for j ∈ [i + 1, 2 kopt ] and j ∈ S do 6: if N[i] < N[j] then 7: Remove item j from the item set S, S = S − j. 8: end if 9: end for 10: end for Suppose after identifying the dominance relation, the size of the search space is reduced from 2kopt to M. Then we can utilize dynamic programming to solve the unbounded two-dimensional knapsack problem. If the deployment area is a circular area with regular shape, then according to the problem formulation in (7), we main￾tain a table F[j][k][l] to denote the maximum reduced energy cost, which can be attained with the following constraints: • It uses items up to the jth kind; • The required number of storages is less than or equal to k; • The required number of items is less than or equal to l. Hence we can define f[j][k][l] recursively as follows:    F[0][k][l] = 0 F[j][k][l] = max0≤xj≤min([ N N[j] ],[ π θ ]) f f = F[j − 1][k − xj · N[j]][l − xj · θ] + xj · E[j] (10) The above formulation shows that when j = 0, no items can be used, the reduced energy cost is 0; otherwise, according to the value of F[j − 1][k − xj · N[j]][l − xj · θ], we can calculate the value of F[j][k][l] by obtaining the maximum value of F[j − 1][k − xj · N[j]][l − xj · θ] + xj · E[j] through enumerating all possible values of xj . Therefore, if we maintain a three-dimensional table F[j][k][l] of size M × N × π θ , we can calculate each value of F[j][k][l] recursively according to the formulation (10), then finally we can obtain the value of f ∗ = F[M][K][ π θ ], which is the maximum reduced energy cost. By tracing back each xj (0 ≤ j ≤ M) used to achieve f ∗ , we can obtain the opti￾mal parameters for the optimal storage placement. Since the computation of f ∗ involves examining M items, and there are K× π θ values of each F[j][k][l] to calculate by using items up to j, the compute complexity of the dynamic program￾ming is O(M · K · π θ ). If the deployment area is in irregular shape, then according to the problem formulation in (8), we can add an additional dimension to denote which partition the current item is put into. Then similarly we can recursively calculate the optimal solution step by step. Hence the compute complexity of the dynamic programming is O(m · M · K · π θ ). 5.4 Greedy Approximation Algorithm We already know that the dynamic programming based al￾gorithm is able to solve the problem in a pseudo-polynomial time. However, as the number of storages, K, increases to a large value, the compute complexity is still fairly large. Therefore, a greedy approximation algorithm is essential to be proposed to solve the above problem in a more time￾efficient approach. Consider the situation with limited number of storages, it can be understood that conventionally the storage is a scarcer resource than the other issues such as the space. Here we use the notion sack to denote the fan-shaped partition. Algo￾rithm 2 illustrates the greedy approximation algorithm. In this algorithm, for any sack-item pair (i, j)(1 ≤ i ≤ m, 1 ≤ j ≤ M), we first sort the pairs in decreasing order of re￾duced energy per storage unit, i.e., E[i][j] N[j] ; then among the pairs with equivalent value of E[i][j] N[j] , we further sort them in decreasing order of reduced energy per degree unit, i.e., E[i][j] θ . As the degree θ is equivalent for all pairs, thus the pairs are actually sorted according to the value of E[i][j]. After that, we proceed to insert the corresponding items into the sacks. Among all sack-item pairs, we start from the sack-item pair (i, j) which ranks first in the sorted pairs, putting as many copies as possible of the item j into the sack i until there is not enough space for the item j in sack i. Then we continue to insert the copies of the items into corresponding sacks according to the ranking of the sack￾item pairs, until there is no longer space for any kind of the item in the corresponding sack for more. Algorithm 2 Greedy Approximation Algorithm 1: Calculate E[i][j] and N[j] for all sack-item pairs (i, j). 2: Sort all the sack-item pairs (i, j) in decreasing order of E[i][j] N[j] . 3: Among the items with equivalent value of E[i][j] N[j] , further sort all the sack-item pairs (i, j) in decreasing order of E[i][j]. 4: Push the ranked sack-item pairs (i, j) into a queue Q. 5: k = K, li = βi θ (i ∈ [1, m]). 6: while k > 0 and li > 0 for at least one sack i do 7: Pop one sack-item pair (i, j) from Q. 8: if li > 0 then 9: Put xi,j copies of item j into sack i, here xi,j = min{li, k N[j] }. 10: end if 11: k = k − xi,j · N[j], li = li − xi,j · θ(i ∈ [1, m]). 12: end while The above greedy approximation algorithm has the following properties in term of performance, as shown in Theorem 3. Theorem 3. Assume Emax is the maximum value of items that fit into the sack in the unbounded knapsack problem, then with limited number of storages, the greedy approxima-