1
The algorithm is a bad approximation algorithm. For example,
we will get flow 10 using this algorithm for the following graph, but the maximum flow of this graph is 20.
2.
Pseudocode :
def goldBars(W, n, w): i=1
golds = [] curretWeight = 0 while i <= n:
if w[i] > W:
# remove bar whose weight is more than W i += 1
continue
if curretWeight + w[i] <= W: curretWeight += w[i] golds.append(i)
i += 1
else:
# adding i bar will exceed limit, break break
# choose bigger one
if i == n+1 or curretWeight > w[i]:
return golds, curretWeight else:
return [i], w[i]
if __name__ == ‘__main__’:
print(goldBars(7, 4, [None, 1, 4, 10, 3])) print(goldBars(7, 4, [None, 1, 4, 10, 6])) print(goldBars(7, 4, [None, 1, 4, 10, 2]))
Proof:
Assume that w[i] <= W for each i, if no such case, we can remove all gold bars whose weight is more than W. From i=1, add w[i] to the knapsack until after adding the a[i], the total weight will be more than W. If after adding all gold bars, the weight is still no larger than W, then obvious the bars solution 1,2,...n is optimal. Suppose w[1] + w[2] + ... w[i-1] = X. First we can see that X <= W and w[i] <= W, so both 1,2,...i-1 and i are valid choice. From algorithm description, We have X + w[i] >= W. Suppose optimal value is OPT, we have OPT <= W, so X + w[i] >= OPT, so either X >= (1/2)OPT or w[i] >= (1/2)OPT, because we choose the bigger one, so our solution must >= (1/2)OPT.
Runtime: The algorithm iterate at most n bars, and in each iteration, it spends const O(1) time, so it runs in O(n). Thus, it is a polynomial, 2-approximation algorithm.