def _knapsack_0(W, vs, ws):
    """
    This is an O(pow(2, n)) inefficient solution that lists all subsets
    """
    value, weight = 0, 0
    for i in range(1, pow(2, len(vs))):
        v, w = 0, 0
        j, k = i, 0
        while j:
            if j % 2:
                v += vs[k]
                w += ws[k]
            k += 1
            j //= 2
            if w > W:
                break
        if value <= v and w <= W:
            value, weight = v, w
    return value
