算法高级教程3.6Theknapsackproblem.pptVIP

for S’, Due I and I’ have the same set of optimum solutions namely S’= S’’ namely, so Due to There are other variations as well, notably the multiple knapsack problem, in which you have more than one knapsack to fill. so so it is FPTAS. The subset-sum problem An instance of the subset-sum problem is a pair (S, t), where S is a set {x1, x2, ..., xn} of positive integers and t is a positive integer. This decision problem asks whether there exists a subset of S that adds up exactly to the target value t. The optimization variant asks for a subset of S whose sum is as large as possible, but not larger than t An exponential-time exact algorithm ExactSubsetSum(S, t) 1 n ← |S| 2 L0 ← 0 3 for i ← 1 to n do 4 Li ← MergeLists(Li-1, Li-1 + xi) 5 remove from Li every element that is greater than t 6 return the largest element in Ln To see how ExactSubsetSum(S, t) works, let Pi denote the set of all values that can be obtained by selecting a (possibly empty) subset of {x1, x2, ..., xi} and summing its members. For example, if S = {1, 4, 5}, then P1 = {0, 1} , P2 = {0, 1, 4, 5} , P3 = {0, 1, 4, 5, 6, 9, 10} A fully polynomial-time approximation scheme We can derive a fully polynomial-time approximation scheme for the subset-sum problem by trimming each list Li after it is created. To trim a list L by δ means to remove as many elements from L as possible, in such a way that if L is the result of trimming L, then for every element y that was removed from L, there is an element z still in L that approximates y, that is, example, if δ = 0.1 and L = 10, 11, 12, 15, 20, 21, 22, 23, 24, 29 then we can trim L to obtain L = 10, 12, 15, 20, 23, 29 Trim(L, δ) 1 m ← |L| 2 L ← y1 3 last ← y1 4 for i ← 2 to m do 5 if yi last · (1 +δ) then 6 append yi onto the end of L 7 last ← yi 8 return L ApproxSubsetSum(S, t ) 1 n ← |S| 2 L0 ← 0 3 for i ← 1 to n do 4