# Fast Polynomial Time Approximate Solution for 0-1 Knapsack Problem

Authors: Zhengyuan Wang; Hui Zhang; Yali Li
Journal: Computational Intelligence and Neuroscience
 (2022)

---

## Abstract

0-1 Knapsack problem (KP) is NP-hard. Approximate solution is vital for solving KP exactly. In this paper, a fast polynomial time approximate solution (FPTAS) is proposed for KP. FPTAS is a local search algorithm. The best approximate solution to KP can be found in the neighborhood of the solution of upper bound for exactk-item knapsack problem (E-kKP) where k is near to the critical item s. FPTAS, in practice, often achieves high accuracy with high speed in solving KP. The computational experiments show that the approximate algorithm for KP is valid.


---

## Body

## 1. Introduction

0-1 Knapsack problem (KP) is a classical combinatorial optimization problem. KP is NP-hard. Knapsack problems were used to model capital budgeting problems in which investment projects are to be selected subject to expenditure limitations. Additionally, the knapsack problem has been used to model loading problems. Knapsack problems, moreover, arise as suboptimization problems in solving larger optimization problem [1]. KP can be formulated as follows:(1)maxfx=∑i=1npixi,s.t,∑i=1nwixi≤c,xi=0,1.i=1,2,⋯,n,where pi is the profit of item i, wi is the weight of item i, c is the capacity of the knapsack, n is the number of items in KP, and variable xi=0or1 indicates whether item i is selected or not. Without loss of generality, it is assumed that all items are arranged in nonincreasing order of efficiency.(2)piwi≥pi+1wi+1i=1,2,⋯,n−1.It is very important to find a fast polynomial approximation for KP in practice. Greedy algorithm [1], an approximate algorithm for KP, is on the basis of certain rules, such as the item being selected with priority over larger efficiency, larger profit, or smaller weight. Greedy algorithm is O(n) time complexity, but it is not an ɛ-approximate algorithm [1]. Approximation algorithm is often k-neighborhood local search method. Increasing the radius k of the neighborhood can improve the accuracy of the approximate algorithm [1, 2]. While PTAS for KP typically require only O(n) storage, all FPTAS are based on dynamic programming and their memory requirement increases rapidly with the accuracy ɛ, which makes them impractical even for relatively big values of ɛ [3]. Heuristics rules are adopted to decrease the calculation in searching accurate approximation, such as harmony search algorithm [4, 5], amoeboid organism algorithm [6], cuckoo search algorithm [5, 7], binary monarch butterfly optimization [8], cognitive discrete gravitational search algorithm [9], bat algorithm [10], and wind driven optimization [11]. Nowadays, it is tend to combine different heuristics together in solving combinatorial optimization problem, such as mixed-variable differentiate evolution [12], self-adaptive differential evolution algorithm [13], two-stage cooperative evolutionary algorithm [14], cooperative water wave optimization algorithm with reinforcement learning [15], and cooperative multi-stage hyper-heuristic algorithm [16]. However, these algorithms cannot guarantee the accuracy of the solution of KP. Meanwhile, these methods for the solution to KP are generally time-consuming. More domain knowledge is necessary for better algorithm. Pisinger gave an exact algorithm for KP [17] which is based on an expanding core. The items not included in the core are certain to be selected or not in the optimal solution, while the items in the core are uncertain to be selected or not in the optimal solution. He found that algorithms solving some kinds of core problem may be stuck by difficult cores [18]. For example, KP is determined by(3)wi=i,pi=10i2+107,c=200020,i=1,2,⋯,104.It is easy to find that the core of KP is [1, 10000], so this problem is difficult to tackle by the exact algorithm in [17]. In this paper, it is easy to get an approximate solution of KP which objective value is 6395122580. The solution can be proved to be the optimal solution.In this paper, a fast polynomial approximate solution is proposed for 0-1 knapsack problems based on the solution of its upper bound. Firstly, an upper bound is presented based on the exactk-item knapsack problem E-kKP in Section 2. Secondly, an initial solution of KP is constructed on the basis of the solution of upper bound of E-kKP in Section 3.1. Thirdly, the approximate solution is proposed to find the best solution in the neighborhood of the initial solution in Section 3.2. In Section 3.3, the best approximation solution is achieved by comparison with number of items changing. In Section 3.4, the calculation for the approximate solution of KP is analyzed. In Section 4, computational experiments of KP are implemented. The results show that the approximate solution proposed in this paper can achieve high accuracy in general. It implicates that the exact solution to KP is similar to the solution to the upper bound. The algorithm proposed here is a fast polynomial approximate solution to KP.


## 2. Upper Bound for KP

If there are exactk objects selected in the knapsack, then KP is an exact k-item knapsack problem E-kKP formulated as follows [3]:(4)maxfx=∑i=1npixi,s.t,∑i=1nwixi≤c,∑i=1nxi=k,xi=0,1.i=1,2,⋯,n.The upper bound of E-kKP may be achieved by Lagrangian relaxation of capacity constraint:(5)Lk,λ=λc+max∑i=1npi−λwiui,s.t,∑i=1nui=k,ui=0,1.i=1,2,⋯,n.Suppose that(6)pdk1−λwdk1≥pdk2−λwdk2≥⋯≥pdkn−λwdkn,wdkk≤wdkk+1.Then(7)Lk,λ=λc+∑i=1kpdki−λwdki.SoLk,λ can be solved by sorting pi−λwi in descending order in O (nlnn) time if λ and k are fixed. The upper bound of E-kKP is formulated as follows:(8)Bk=minλ≥0Lk,λ.It can be proved thatLk,λ is a unimodal function of λ if k is fixed. Bk can be quickly solved by linear search algorithm [19]. So Bk can be solved in O (nlnn) time.The upper bound of KP is the maximum value ofBk:(9)B=max0≤k≤nBk.It can be proved thatBk increases when k<s−1 and decreases when k>s, where the critical item s satisfies.(10)0≤c−w1−w2−⋯−ws−1<ws.So the upper bound of KP is(11)B=minBs−1,Bs.Example 1.
Consider the instance of KP listed in Table1. The capacity is 467.8435.
Here the critical items is 20. There is no feasible solution with 20 items included in the knapsack. So the upper bound B20= 0. If k is 19, we have the optimal ratio λ19 = 1.0003251 and the upper bound B19 = 486.9565 by (8). The solution of L19,λ19 is u19=ud19ias follows:(12)ud19i=1,i≤19,0,i>19,d19i=2,1,4,7,5,3,10,6,9,16,8,13,18,11,26,20,21,17,14,27,28,23,12,15,19,30,25,24,22,29.
So the upper bound of KP is 486.9565.
We test different upper bounds of KP from Pisinger’s paper [20], where the weights and profits of items are randomized. The instances listed in Table2 are tested to compare our proposed method with the existing upper bounds, such as the upper bound UMT2 proposed by Martello and Toth [21], the improved upper bound UMTM [22] and the upper bound Ukmax with maximum cardinality [23]. The difficult instances can be constructed as follows [20]:(i)
Uncorrelated instances with similar weights: Weightswi are distributed in [R, R + 100] and the profits pi in [1, 1000].(ii)
Uncorrelated data instances:pi and wi are chosen randomly in [1, R].(iii)
Weakly correlated instances: Weightswi are chosen randomly in [1, R] and the profits pi in [wi − 0.1 R, wi + 0.1 R] such that pi≥1.(iv)
Strongly correlated instances: Weightswi are distributed in [1, R] and pi = wi + 0.1R.(v)
Inverse strongly correlated instances: Profitspi are distributed in [1, R] and wi = pi+0.1R.(iv)
Almost strongly correlated instances: Weightswi are distributed in [1, R] and the profits pi in [wi + 0.098R, wi + 0.102R].(vii)
Subset sum instances: Weightswj are randomly distributed in [1, R] and pi = wi.(viii)
Circle instances circle (d): The weights are uniformly distributed in [1, R] and for each weight w the corresponding profit is chosen as p=d4wR−w2 where d is 2/3.(ix)
Profit ceiling instances pceil (d): The weights of the n items are randomly distributed in [1, R], and the profits are set to pi=d⌈wi/d⌉. The parameter d was chosen as d = 3.(x)
Multiple strongly correlated instances mstr (k1, k2, d): The weights of the n items are randomly distributed in [1, R]. If the weight wi is divisible by d, then we set the profit pi: = wi + k1; otherwise set it to pi: = wi + k2. We set d: = 6 here.
For each instance type, a series ofK = 100 instances is performed, and the capacity is determined by (13). All the instances above are generated with data range R = 103, 104, 105, 106 or 107.(13)c=k1+K∑i=1nwi,k=1,2,⋯,K.
There are 100 instances for each type of KP where the capability is described as follows:(14)C=k101∑i=1nwi,k=1,2,⋯,100,n=104.
The mean relative error of upper bounds to the best upper bound of KP is listed in Table3.
From Table3, we find that the relative error of the upper bound B is the minimum in general. The upper bounds of 5000 instances are carried out with different methods. More details are listed in Table 4.
From Table4, we find that Ukmax is the best upper bound in 2025 instances. The upper bound B plays an important role in obtaining the best upper bound even if s≤kmax.
The upper bound can gather most items selected in the optimal solution all together. For example, KP is determined by(15)wi=i,pi=10i2+107,c=200020,i=1,2,⋯,104.
A maximum of 631 items can be selected in the knapsack. The upper boundBs−1s=632 and the solution us−1 are as follows:(16)Bs−1=minλ≥0maxλc+∑i=110000pi−λwixi∑i=110000xi=s−1,xi=0,1=106310c+∑i=1631pi−106310wi=7215794600,ui=1,i=1,2,...,631,0,0,631<i≤10000.
The initial solutionzs−1 is equal to us−1. The best solution yas−1 in the neighborhood ∪h=14Nzs−1,2h can be described as follows:(17)yi=1,i=1,2,...,630,1225,0,i≠1225,630<i≤10000.
It is obviously that there is little difference betweenzs−1 and yas−1. Relation between pi−106310wi and wi is displayed in Figure 1. Relation between pi/wi and wi is displayed in Figure 2. It is found that pi−106310wi changes more dramatically than pi/wi. It makes solution to KP easy.
From Figure1, we can see that pi−106310wi of all items selected are larger, while the others are smaller. It is easy to get a better solution on the basis of pi−106310wi than that on the basis of efficiency pi/wi.Table 1
Weight and profit of items.
iwipi11.78562.792424.8775.885336.34937.352147.09438.099257.88078.88568.55939.5616713.924914.9319819.611420.6148921.088122.09251024.268825.27671127.344128.34721231.61832.61891332.773933.77971432.78733.78981533.936834.93791637.156638.16621737.88738.8921839.610440.61751940.01441.01592040.736241.74322142.456543.4632245.289646.28992345.668846.66932445.786846.79322546.699747.70132647.858348.8662747.875348.88482847.974648.98222948.244449.24483048.529649.5335Table 2
Weights and profits of knapsack problems from Pisinger’s paper [20].
No.(wi, pi) (i = 1, 2, …, 104)No.(wi, pi) (i = 1, 2, …, 104)1R+100ui,⌈1000vi⌉2⌈Rui⌉,⌈Rvi⌉3Rui,Rui+0.2vi−0.14Rui,Rui+0.1R5Rvi+0.1R,Rvi6Rui+0.098R,Rui+0.102R7⌈Rui⌉,⌈Rui⌉8Rui,2R/3ui4−ui9Rui,⌈Rui/3⌉10Rui,Rui+0.3R,Rui%6=0;Rui,Rui+0.2R,Rui%6≠0∗Note. ui and vi are uniformly distributed in [0,1]. R = 103, 104, 105, 106 or 107.Table 3
Mean relative error of upper bounds to the best upper bound of (KP) (ppm).
(No,R)UMT2UMTMUkmaxB(No,R)UMT2UMTMUkmaxB(1, 103)4.66964.66964.68690(2, 103)0.01380.00310.04210.0174(1, 104)91.41391.386981.44220(2, 104)0.03450.00750.04650.0189(1, 105)60.260760.254243.27650(2, 105)0.01940.0050.03510.0164(1, 106)61.036661.036600(2, 106)0.02580.00570.03910.0152(1, 107)61.337261.337200(2, 107)0.02740.00690.04660.018(3, 103)0.01160.00490.01790(4, 103)28.787628.787600(3, 104)0.003100.01960.0044(4, 104)34.65634.651800(3, 105)0.01480.00180.0270.016(4, 105)31.553531.545600(3, 106)0.01140.00160.01660.0071(4, 106)27.508227.500100(3, 107)0.00660.00220.01050.0031(4, 107)25.749325.746700(5, 103)38.905438.905438.90540(6, 103)0000(5, 104)0000(6, 104)0000(5, 105)0000(6, 105)0000(5, 106)0000(6, 106)0000(5, 107)0000(6, 107)0000(7, 103)0000(8, 103)0000(7, 104)0000(8, 104)0000(7, 105)0000(8, 105)22.860222.860200(7, 106)0000(8, 106)0000(7, 107)0000(8, 107)0000(9, 103)0000(10, 103)0000(9, 104)0000(10, 104)0000(9, 105)16.134416.134400(10, 105)0000(9, 106)30.144730.144700(10, 106)0000(9, 107)8.91568.91568.91560(10, 107)0000∗The best upper bound is min{UMT2, UMTM, Ukmax, B} in this paper.Table 4
Sum of the best upper bounds in 5000 instances.
Upper boundSum of the best upper boundPercentage of the best upper bound (%)Sum of the best upper bounds equal toBUMT2152030.401495UMTM192538.501548Ukmax202540.502025B462392.464623Figure 1
Relation betweenpi−106310wi and wi.Figure 2
Relation between (pi/wi) and wi.


## 3. Approximate Solutions

The approximate solution to E-kKP is a solution to KP. We obtain the best approximate solution to KP by comparison to approximate solutions for E-kKP where k is near to the critical item s. In order to achieve a better solution to E-kKP, we firstly obtain an initial solution on the basis of the solution to the upper bound of E-kKP. Then the initial solution is developed by local search in the neighborhood of the initial solution. At last, the approximate solution to KP is the best approximate solution to E-kKP with various k. The upper bound of E-kKP is used to decrease calculation. The solution to the upper bound of E-kKP and the upper bound make key contribution in FPTAS to KP.


### 3.1. Initial Solution to E-kKP

Letuk=udki be an optimal solution to the upper bound Bk. We may obtain an initial solution to E-kKP on the basis of uk. The initial solution zk to E-kKP is determined by(18)udki=1,i≤k,0,k<i≤n,zdki=udki,i≠k,k+1,udki,wdkk+1>c−∑j=1k−1wdkj,i=k,k+1,1−udki,wdkk>c−∑j=1k−1wdkj,i=k,k+1,udki,c−∑j=1k−1wdkj≥maxwdkk,wdkk+1,pdkk≥pdkk+1,i=k,k+1,1−udki,c−∑j=1k−1wdkj≥maxwdkk,wdkk+1,pdkk<pdkk+1,i=k,k+1.In Example 1,z19 is an initial solution and its objective value is(19)fz19=473.1749Zd19i=1,i≤190,i>19d19i=2,1,4,7,5,3,10,6,9,16,8,13,18,11,26,20,21,17,14,27,28,23,12,15,19,30,25,24,22,29.


### 3.2. Approximate Solution to E-kKP

Approximate solution to E-kKP is the best solution in the neighborhood of zk. Let Nzk,2h be a neighborhood of zk that is defined by(20)Nzk,2h=yk=ydki∑i=1nydki−zdki=2h,∑i=1nydki=k,ydki=0,1.It is obvious that the size ofNzk,2h increases with h. But it is unnecessary to take into account all elements of Nzk,2h. Algorithm 1 is a fast algorithm for searching the best solution in Nzk,2h.Algorithm 1: Approximate solution to (E-kKP).
Step 1: Obtain the neighborhoodNzk,2h by (20), h = 1, 2, 3, 4.Step 2: Calculate the objective value of feasible solutionyk=ydki in Nzk,2h by equation as follows: fyk=∑i=1npiydki,∑i=1nwiydki≤c0,∑i=1nwiydki>cStep 3: Obtain the best solutionyak in Nzk,2hh=1,2,3,4 by (Algorithm 1). fyak=maxfykyk∈∪h=14Nzk,2hIn order to decrease the calculation for the approximate solution to KP,Nzk,2h is redefined by (21) and Step 1 in Algorithm 1 is modified correspondingly.(21)Nzk,2h=yk=ydki∑i=LkhUkhydki−zdki=2h,∑i=1nydki=k,ydki=0,1,where(22)Lkh=1,h=1maxk−100,1,h=2max1,k−50,h=3maxk−30,1,h=4Ukh=n,h=1min99+k,n,h=2min49+k,n,h=3min29+k,n,h=4s−5≤k≤s+4.From (21), we know that the size of Nzk,2hh=1,2,3,4 is limited. In order to search for the best solution, it is unnecessary to seek all solutions in Nzk,2h. Let(23)rw=c−wdk1−wdk2−⋯−wdkkps1,ws1|ps1=pdki1+⋯+pkih,ws1=wdki1+⋯+wdkih+rw,max1,Lkh≤i1<⋯<ih≤kps2,ws2|ps2=pdkj1+⋯+pdkjh,ws2=wdkj1+⋯+wdkjh,k<j1<⋯<jh≤minn,Ukh.The best approximate solution corresponds tomaxps2−ps1ws2≤ws1, so the calculation is O (nlnn) time when h equals to 1. A better solution is generated if the profit sum of h items selected in the knapsack is less than that of h items not selected in the knapsack, and the capacity constraint still holds at the same time. On the other hand, the calculation decreases via variable reduction in practice.In Example 1, let the approximate solutionxa equal to z19 and objective value fa equal to fz19 firstly, and then the approximate solution xa is updated by the best solution ya19 in Nz19,2 if possible.(24)fya19=486.1884>fa=473.1749yd19i=zd19i,i≤30,i≠12,221−zd19i,i=12,22fa←fya19,xa←ya19.Similarly,xa is replaced by the best solution ya19 in Nz19,4 if possible.(25)fya19=486.9426>fa=486.1884yd19i=1,i=1,2,...,21,i≠13,170,i=13,17,22,...,30fa←fya19,xa←ya19.There is no better solution of KP inNz19,6 and Nz19,8. We get an approximate solution ya19 with 19 items selected and the approximate objective value is 486.9426.


### 3.3. Approximation Algorithm of KP

Letxa describe the best approximate solution to KP in (26).(26)xa=argmaxkfyak=argmaxkmax1≤h≤4fykyk∈Nzk,2h.We can obtain the approximate solutionxa of KP by Algorithm 2.Algorithm 2: Approximate Algorithm for (KP).
Step 1 Input the capacityc, size n, weights wi and profits pi of items.Step 2 Obtain the critical items by (10).Step 3 Let=0,0,...,0,fa=0,k1=s−1,k2=s.Step 4 Obtain the upper boundBk and its solution ukk=k1,k2 by (8).Step 5 IfBk1≥Bk2, then k=k1. Otherwise, k=k2.Step 6 IfBk≤fa, then exit.Step 7 Obtain the initial solutionzk by (18).Step 8 Obtain the best solutionyak in the neighborhood Nzk,2hh=1,2,3,4 and its objective value fyak by Algorithm 1.Step 9 Iffa<fyak, then fa←fyak,xa←yak.Step 10 Ifk=k1, then k1←k1−1, get Bk1 and its solution uk1 by (8); else, k2←k2+1, get Bk2 and its solution uk2 by (8). Go to Step 5.In Example1, we obtain fa=486.9426 when k = 19.(27)B20=0,B18=485.9582<fa=486.9426.The best approximate solutionxa=xd19i for KP and its objective value are as follows:(28)fa=486.9426.It may be proved thatxa is the optimal solution to KP in Example 1.


### 3.4. Calculation Analysis

Approximation algorithms for KP based on upper bound of E-kKP runs in polynomial time. Calculation for the upper bound of E-kKP is less than O (nlnn) for a given E-kKP. We obtain the approximate solution to KP on the basis of the upper bound of E-kKP where k is an integer close to s. For a given k, the initial solution is determined by (13). It takes O (nlnn) time to develop the initial solution in the neighborhood Nzk,h (h = 1, 2, …, 4) defined by (21). Hence, it takes at most O (nlnn) time to achieve the approximate solution to E-kKP. Generally, we obtain the best approximate solution for KP among the approximate solutions for E-kKP where k is near the critical item s. Hence, the calculation for approximate solution to KP is less than O (nlnn).In Algorithm1, we search for the best solution in Nzk,h defined by (21). In order to develop the approximate solution quickly, the weight sum of h items is sorted in ascending order firstly, and then the profit sum of h items selected in the knapsack is compared with the profit sum of h items not selected. So the storage needed in Algorithm 1 is O(n) when h is fixed at 1, 2, 3, or 4. In Algorithm 2, we have the best solution to KP by comparison to the best approximate solution to E-kKP where k is an integer close to s. So the storage of the approximate algorithm for KP is O(n).


### 3.5. Accuracy Analysis

All feasible solutions to KP are in the search scope of approximation algorithm with changingk and h. So approximation algorithm for KP is an ε-approximation algorithm. From one aspect, weights, profits, capacity and size of KP have influence on the accuracy of an approximation algorithm. From another aspect, the search scope of the approximation algorithm has influence on its accuracy as well. Better solution is usually with more calculation. The exact algorithm for KP may be explored on the basis of the branch and bound algorithm here. Intensive research will be carried out in the future.


## 3.1. Initial Solution to E-kKP

Letuk=udki be an optimal solution to the upper bound Bk. We may obtain an initial solution to E-kKP on the basis of uk. The initial solution zk to E-kKP is determined by(18)udki=1,i≤k,0,k<i≤n,zdki=udki,i≠k,k+1,udki,wdkk+1>c−∑j=1k−1wdkj,i=k,k+1,1−udki,wdkk>c−∑j=1k−1wdkj,i=k,k+1,udki,c−∑j=1k−1wdkj≥maxwdkk,wdkk+1,pdkk≥pdkk+1,i=k,k+1,1−udki,c−∑j=1k−1wdkj≥maxwdkk,wdkk+1,pdkk<pdkk+1,i=k,k+1.In Example 1,z19 is an initial solution and its objective value is(19)fz19=473.1749Zd19i=1,i≤190,i>19d19i=2,1,4,7,5,3,10,6,9,16,8,13,18,11,26,20,21,17,14,27,28,23,12,15,19,30,25,24,22,29.


## 3.2. Approximate Solution to E-kKP

Approximate solution to E-kKP is the best solution in the neighborhood of zk. Let Nzk,2h be a neighborhood of zk that is defined by(20)Nzk,2h=yk=ydki∑i=1nydki−zdki=2h,∑i=1nydki=k,ydki=0,1.It is obvious that the size ofNzk,2h increases with h. But it is unnecessary to take into account all elements of Nzk,2h. Algorithm 1 is a fast algorithm for searching the best solution in Nzk,2h.Algorithm 1: Approximate solution to (E-kKP).
Step 1: Obtain the neighborhoodNzk,2h by (20), h = 1, 2, 3, 4.Step 2: Calculate the objective value of feasible solutionyk=ydki in Nzk,2h by equation as follows: fyk=∑i=1npiydki,∑i=1nwiydki≤c0,∑i=1nwiydki>cStep 3: Obtain the best solutionyak in Nzk,2hh=1,2,3,4 by (Algorithm 1). fyak=maxfykyk∈∪h=14Nzk,2hIn order to decrease the calculation for the approximate solution to KP,Nzk,2h is redefined by (21) and Step 1 in Algorithm 1 is modified correspondingly.(21)Nzk,2h=yk=ydki∑i=LkhUkhydki−zdki=2h,∑i=1nydki=k,ydki=0,1,where(22)Lkh=1,h=1maxk−100,1,h=2max1,k−50,h=3maxk−30,1,h=4Ukh=n,h=1min99+k,n,h=2min49+k,n,h=3min29+k,n,h=4s−5≤k≤s+4.From (21), we know that the size of Nzk,2hh=1,2,3,4 is limited. In order to search for the best solution, it is unnecessary to seek all solutions in Nzk,2h. Let(23)rw=c−wdk1−wdk2−⋯−wdkkps1,ws1|ps1=pdki1+⋯+pkih,ws1=wdki1+⋯+wdkih+rw,max1,Lkh≤i1<⋯<ih≤kps2,ws2|ps2=pdkj1+⋯+pdkjh,ws2=wdkj1+⋯+wdkjh,k<j1<⋯<jh≤minn,Ukh.The best approximate solution corresponds tomaxps2−ps1ws2≤ws1, so the calculation is O (nlnn) time when h equals to 1. A better solution is generated if the profit sum of h items selected in the knapsack is less than that of h items not selected in the knapsack, and the capacity constraint still holds at the same time. On the other hand, the calculation decreases via variable reduction in practice.In Example 1, let the approximate solutionxa equal to z19 and objective value fa equal to fz19 firstly, and then the approximate solution xa is updated by the best solution ya19 in Nz19,2 if possible.(24)fya19=486.1884>fa=473.1749yd19i=zd19i,i≤30,i≠12,221−zd19i,i=12,22fa←fya19,xa←ya19.Similarly,xa is replaced by the best solution ya19 in Nz19,4 if possible.(25)fya19=486.9426>fa=486.1884yd19i=1,i=1,2,...,21,i≠13,170,i=13,17,22,...,30fa←fya19,xa←ya19.There is no better solution of KP inNz19,6 and Nz19,8. We get an approximate solution ya19 with 19 items selected and the approximate objective value is 486.9426.


## 3.3. Approximation Algorithm of KP

Letxa describe the best approximate solution to KP in (26).(26)xa=argmaxkfyak=argmaxkmax1≤h≤4fykyk∈Nzk,2h.We can obtain the approximate solutionxa of KP by Algorithm 2.Algorithm 2: Approximate Algorithm for (KP).
Step 1 Input the capacityc, size n, weights wi and profits pi of items.Step 2 Obtain the critical items by (10).Step 3 Let=0,0,...,0,fa=0,k1=s−1,k2=s.Step 4 Obtain the upper boundBk and its solution ukk=k1,k2 by (8).Step 5 IfBk1≥Bk2, then k=k1. Otherwise, k=k2.Step 6 IfBk≤fa, then exit.Step 7 Obtain the initial solutionzk by (18).Step 8 Obtain the best solutionyak in the neighborhood Nzk,2hh=1,2,3,4 and its objective value fyak by Algorithm 1.Step 9 Iffa<fyak, then fa←fyak,xa←yak.Step 10 Ifk=k1, then k1←k1−1, get Bk1 and its solution uk1 by (8); else, k2←k2+1, get Bk2 and its solution uk2 by (8). Go to Step 5.In Example1, we obtain fa=486.9426 when k = 19.(27)B20=0,B18=485.9582<fa=486.9426.The best approximate solutionxa=xd19i for KP and its objective value are as follows:(28)fa=486.9426.It may be proved thatxa is the optimal solution to KP in Example 1.


## 3.4. Calculation Analysis

Approximation algorithms for KP based on upper bound of E-kKP runs in polynomial time. Calculation for the upper bound of E-kKP is less than O (nlnn) for a given E-kKP. We obtain the approximate solution to KP on the basis of the upper bound of E-kKP where k is an integer close to s. For a given k, the initial solution is determined by (13). It takes O (nlnn) time to develop the initial solution in the neighborhood Nzk,h (h = 1, 2, …, 4) defined by (21). Hence, it takes at most O (nlnn) time to achieve the approximate solution to E-kKP. Generally, we obtain the best approximate solution for KP among the approximate solutions for E-kKP where k is near the critical item s. Hence, the calculation for approximate solution to KP is less than O (nlnn).In Algorithm1, we search for the best solution in Nzk,h defined by (21). In order to develop the approximate solution quickly, the weight sum of h items is sorted in ascending order firstly, and then the profit sum of h items selected in the knapsack is compared with the profit sum of h items not selected. So the storage needed in Algorithm 1 is O(n) when h is fixed at 1, 2, 3, or 4. In Algorithm 2, we have the best solution to KP by comparison to the best approximate solution to E-kKP where k is an integer close to s. So the storage of the approximate algorithm for KP is O(n).


## 3.5. Accuracy Analysis

All feasible solutions to KP are in the search scope of approximation algorithm with changingk and h. So approximation algorithm for KP is an ε-approximation algorithm. From one aspect, weights, profits, capacity and size of KP have influence on the accuracy of an approximation algorithm. From another aspect, the search scope of the approximation algorithm has influence on its accuracy as well. Better solution is usually with more calculation. The exact algorithm for KP may be explored on the basis of the branch and bound algorithm here. Intensive research will be carried out in the future.


## 4. Computational Experiments

By Algorithm2, we get the approximate solutions to KP listed in Table 5. The results are listed in Table 6. The optimal value listed in Table 6 is carried out by combo [24].Table 5
0/1 Knapsack problems.
No.(wi, pi) (i = 1, 2, …, 10000)C1i,i2.6e + 072i,lni+12.7e + 073i,tanπi/300002.8e + 074i,100+10−4i22.9e + 075i,0.01i−56002+13.0e + 076i,i+tanπi/300003.1e + 077i,tanπi/30000+0.001i23.2e + 078i,5000+10−6i33.3e + 079i,tanπi/30000+10−6i33.4e + 0710i,arctan0.01i+13.5e + 0711i,3−lncos10−4i3.6e + 0712i,arctan10−4i2+13.7e + 0713i,sine10−4i+10−4i23.8e + 0714i,sine10−4i+10−2i3.9e + 0715i,1/i4.0e + 0716i,e10−4i+e−10−4i/sin10−4i4.1e + 0717i,i24.2e + 0718i,i+2+εi,εi∼0,0.0034.3e + 07Table 6
Approximate value and optimization value of 0/1 Knapsack problems.
No.Approximate valueOptimal value14.082159596963170e + 054.082159596963174e + 0526.541219347026785e + 046.541219347026781e + 0434.102160742890480e + 034.102160742890481e + 0342.462154058619999e + 072.462154058620000e + 0758.338180285999998e + 088.338180286000001e + 0863.100447382723671e + 073.100447382723672e + 0772.613912845586523e + 072.613912845586526e + 0782.232528710024500e + 092.232528710024500e + 0992.244286940564110e + 092.244286940564110e + 09102.096538351264514e + 042.096538351264514e + 04112.655627458756987e + 042.655627458756988e + 04122.189122733748200e + 042.189122733748204e + 04132.942021969836180e + 072.942021969836181e + 07143.981146835799920e + 053.981146835799920e + 05159.6758979558557239.675897955855723161.997554888239176e + 051.997554888239177e + 05173.120269950000000e + 113.120269950000000e + 11184.301855990805434e + 074.301855990837396e + 07From Table6, we find that the approximate solutions are almost the optimal solutions in 18 instances. It implicates that the approximate algorithm proposed here achieves high precision in solving KP.In Table7 lists the experimental results of the solutions for KP listed in Table 2 by Algorithm 2. The upper bound listed in Table 4 is carried out by equation (11) in Section 2.Table 7
Relative average error to the upper bound (ppm).
RNo. 1No. 2No. 3No. 4No. 5No. 6No. 7No. 8No. 9No. 101035.65792.70821.64690.400301.28830.0573100.535141.054724.88551040.32271.52080.72580.01570.01320.4878046.70070.13121.44831050.05911.14470.48770.01410.04440.23570.004443.65940.014819.16981060.05771.15240.67310.01850.03280.2460.004750.01260.001419.211070.05101.2050.58000.02290.01920.19750.003449.97640.000114.8858From Table7, we see that the relative average error of 100 instances is almost less than 0.0001. The experiment result shows that the approximate algorithm proposed here can achieve high accuracy.From Table8, we find that the upper bound of E-kKP makes key contribution in FPTAS. Firstly, the initial solution constructed on the basis of the solution to the upper bound of E-kKP is similar with the optimal solution. For example, there are only 4 elements different between the initial solution and the optimal solution to E-kKP where k equals to 19, while there are 8 elements different between the initial solution constructed by efficiency and the optimal solution to KP in Table 8. Secondly, the differences between the initial solution and the solution to the upper bound of E-kKP are near to the item dkk. It is to say, we search the optimal solution to KP in a core with small size on the basis of the solution to the upper bound of E-kKP. While the optimal solution to KP in a core with large size on the basis of the solution to the upper bound of Dantzig. So, algorithms proposed here is easy to get approximate solution to KP.Table 8
Relation between (pi-1.0003121wi) and the optimal solution xiopt in Example 1.
iwipipi/wiejpi−1.0003121wid19lxioptxieizi1924.8775.88531.2067459521.006714385111111.78562.79241.56384408611.006219464211147.09438.09921.14164892941.0025934943111713.924914.93191.07231649871.002472723411157.88078.8851.12743791851.001737819511136.34937.35211.1579386731.00073570961111024.268825.27671.04153069101.000009703711168.55939.56161.11710069760.9995171928111921.088122.09251.04762875790.99754381691111637.156638.16621.027171485160.99751960910111819.611420.61481.05116411980.997023922111111332.773933.77971.030689054130.995144517121111839.610440.61751.025425141180.994221827130111127.344128.34721.03668433110.994209859141112747.875348.88481.02108603260.993934735151012040.736241.74321.024720028200.993755806161012142.456543.4631.023706617210.9926965170011737.88738.8921.026526249170.992682141181112647.858348.8661.021055909270.992140262191001432.78733.78981.030585293140.992140258201112847.974648.98221.021002781280.99200245211002445.786846.79321.021980134230.99151375220001231.61832.61891.031656019120.990620324230101533.936834.93791.029498951150.990066434240101940.01441.01591.025038736190.988890608250103048.529649.53351.020686344300.988122008260002546.699747.70131.021447675250.986416947270002345.668846.66931.021907736240.985652114280002245.289646.28991.022086748220.9855754290002948.244449.24481.020736085290.98471473230000∗pd19l−1.0003121wd19l≥pd19l+1−1.0003121wd19l+1,pej/wej≥pej+1/wej+1,j,l=1,2,⋯,29. xiei is an initial solution constructed in descending order of efficiency.Furthermore, no better solution of E-kKP exists when the objective value fa of the approximate solution achieved before is larger than the upper bound Bk. So we only search solution of E-kKP with upper bound larger than fa which is in the neighborhood of the optimal solution to the upper bound of E-kKP. The candidate strategy makes the search in polynomial time and the solution with high accuracy in Algorithm 1. The upper bound of E-kKP plays important role in decreasing calculation of the approximate solution of E-kKP in Algorithm 2 as well.


## 5. Conclusion

It is still difficult to obtain the exact solution for large scale 0-1 knapsack problem directly. Here a fast polynomial approximate solution is proposed on the basis of the upper bound for KP. The exact solution to KP is in the neighborhood of the solution to the upper bound for E-kKP. Therefore, it is possible to find an approximation with high accuracy in the neighborhood of the solution to the upper bound for E-kKP where k is near to the critical item s. All in all, as the basis of fast exact algorithm for KP, it is important to obtain an approximate solution and the upper bound for KP. In order to obtain a fast exact solution to KP, more intensive research on variables reduction need be conducted in the future.



---

*Source: 1266529-2022-10-22.xml*