正在加载图片...
Scaling Rounding Instance:n items i=1,2,...,n; weights w1,,wn∈Z+;valuesv1,,yn∈Zt; knapsack capacity B EZ; DP with truncated precision: Set k (to be determined); for i=1.2....,n:let v=vk; return the knapsack solution found by DP using new values v(but old weights w;and capacity B); Vi 三 k max max vi 1≤i≤nScaling & Rounding 0 vi : ⏟ k vmax = max 1≤i≤n vi DP with truncated precision: Set (to be determined); for : let ; return the knapsack solution found by DP using new values (but old weights and capacity ); k = i = 1,2,…, n v′ i = ⌊vi/k⌋ v′ i wi B Instance: items ; weights ; values ; knapsack capacity ; n i = 1,2,…, n w1,…,wn ∈ ℤ+ v1,…, vn ∈ ℤ+ B ∈ ℤ+
<<向上翻页向下翻页>>
©2008-现在 cucdc.com 高等教育资讯网 版权所有