Advanced Algorithms Rounding Data 尹一通Nanjing University,2022Fall
尹⼀通 Nanjing University, 2022 Fall Advanced Algorithms Rounding Data
Knapsack Problem Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;valuesv1,,yn∈Zt; knapsack capacity BEZ; Find a subset of items whose total weight is bounded by B and total value is maximized. weight6 capacity B weight values value weight value2 weights values weight3 value3 value4
Knapsack Problem Instance: items ; weights ; values ; knapsack capacity ; Find a subset of items whose total weight is bounded by and total value is maximized. n i = 1,2,…, n w1, …,wn ∈ ℤ+ v1,…, vn ∈ ℤ+ B ∈ ℤ+ B weight1 value1 weight2 value2 weight3 weight value3 4 value4 weight5 value5 weight6 value6 capacity B
Knapsack Problem Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;values v1,,yn∈Zt; knapsack capacity B E; Find an S {1,...,n}that maximizes ∑es subject to∑icsW:≤B. weight6 capacity B weight ·0-1 Knapsack value6 value problem ·one of Karp's21 weight value2 NP-complete problems weights values weight3 OO元eigh value3 value4
Knapsack Problem Instance: items ; weights ; values ; knapsack capacity ; Find an that maximizes subject to . n i = 1,2,…, n w1,…,wn ∈ ℤ+ v1,…, vn ∈ ℤ+ B ∈ ℤ+ S ⊆ {1,…, n} ∑i∈S vi ∑i∈S wi ≤ B weight1 value1 weight2 value2 weight3 weight value3 4 value4 weight5 value5 weight6 value6 capacity B • 0-1 Knapsack problem • one of Karp’s 21 NP-complete problems
Greedy Can Fail Badly Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;valuesv1,,yn∈Z+； knapsack capacity B E+; Find an S)that maximizes s subject to∑icsM≤B. Greedy Fit: Sort items non-decreasingly in v:/w; scan items one-by-one in that order,for each item: include the item in the knapsack if it fits; approximation ratio:arbitrarily bad
Greedy Can Fail Badly Instance: items ; weights ; values ; knapsack capacity ; Find an that maximizes subject to . n i = 1,2,…, n w1,…,wn ∈ ℤ+ v1,…, vn ∈ ℤ+ B ∈ ℤ+ S ⊆ {1,…, n} ∑i∈S vi ∑i∈S wi ≤ B Greedy Fit: Sort items non-decreasingly in ; scan items one-by-one in that order, for each item: include the item in the knapsack if it fits; vi/wi approximation ratio: arbitrarily bad
Dynamic Programming Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;values v1,,yn∈Zt; knapsack capacity B E; 。Define: A(i,v)minimum total weight of S {1,2,...,i} with total value exactly v A(i,v)oo if no such S exists Answer to the knapsack problem: max{v|A(n,v)≤B}
• Define: • Answer to the knapsack problem: max {v ∣ A(n, v) ≤ B} Dynamic Programming Instance: items ; weights ; values ; knapsack capacity ; n i = 1,2,…, n w1,…,wn ∈ ℤ+ v1,…, vn ∈ ℤ+ B ∈ ℤ+ minimum total weight of with total value exactly A(i, v) ≜ S ⊆ {1,2,…, i} v A(i, v) ≜ ∞ if no such S exists