gistfile1.py

# coding: utf-8

def dfs(i, w, c, x):
    if i == len(w):
        return True

    wi = w[i]
    for j in range(len(c)):
        if wi > c[j]:
            continue

        new_c = list(c)
        new_c[j] -= wi
        x[i] = j
        is_feasible = dfs(i + 1, w, new_c, x)
        if is_feasible:
            return True
    return False


def solve(w, c):
    if sum(w) > sum(c):
        raise Exception('No feasible solution')

    x = [None] * len(w)
    is_feasible = dfs(0, w, c, x)
    if is_feasible:
        return x
    else:
        raise Exception('No feasible solution')


def gen(d, n):
    from random import randrange

    w = [randrange(10, 100) for _ in range(n)]
    v = sum(w) // d
    c = [randrange(max(1, v - 20), v + 20) for _ in range(d)]
    return w, c
    

def main():
    import sys

    sys.setrecursionlimit(10000)
    #d = int(input())
    #c = [int(input()) for _ in range(d)]
    #n = input()
    #w = [int(input()) for _ in range(n)]
    w, c = gen(3, 1000)
    w.sort(reverse=True)
    solution = solve(w, c)
    print(solution)


if __name__ == '__main__':
    main()