Submission #287540

---

Source Code Expand

def depth_first_search(w, n, k, ABs):
    def _greedy_by_width(index, w):
        val = 0
        width = 0
        for a, b in ABs[index:]:
            if a > w:
                continue
            elif width + a < w:
                width += a
                val += b
            else:
                val += b * (w - width) * 1.0 / (a*1.0)
                break
        return val
    
    def _greedy_by_num(index, k):
        bs = Bs[index:]
        bs.sort(reverse=True)
        return sum(bs[:k])
 
    def _dfs(w, index, k, val, best_val):
        if val > best_val[0]:
            best_val[0] = val
        if k == 0 or index == n:
            return
        a, b = ABs[index]
        dif = best_val[0] - val
        if _greedy_by_width(index, w) <= dif:
            return
        if _greedy_by_num(index, k) <= dif:
            return
        if w >= a:
            _dfs(w - a, index + 1, k - 1, val + b, best_val)
        _dfs(w, index + 1, k, val, best_val)
 
    Bs = [b for a, b in ABs]
    best_val = [0]
    index = 0
    val = 0
    _dfs(w, index, k, val, best_val)
    return best_val[0]
 
 
def read_problem():
    W = int(raw_input())
    N, K = map(int, raw_input().split())
    ABs = []
    for i in range(N):
        ABs.append(tuple(map(int, raw_input().split())))
    return W, N, K, ABs
 
if __name__ == '__main__':
    W, N, K, ABs = read_problem()
    ABs.sort(key=lambda x: x[1] * 1.0 / (x[0] * 1.0), reverse=True)
    ans = depth_first_search(W, N, K, ABs)
    print(ans)

Submission Info

Judge Result