credit

gistfile1.py

def solve(cost, els):
    total = [
        [(0, -1)] * (cost + 1)
        for _ in xrange(len(els) + 1)
    ]

    for idx, el in enumerate(els):
        idx += 1
        for current_cost in xrange(cost + 1):
            if el > current_cost:
                total[idx][current_cost] = max(total[idx][current_cost - 1],
                                               total[idx-1][current_cost])
            else:
                b_cost, b_idx = total[idx-1][current_cost - el]
                if el + b_cost == cost and b_idx != -1:
                    return sorted([idx, b_idx])
                else:
                    total[idx][current_cost] = max(
                        (el, idx,),
                        total[idx-1][current_cost]
                    )


def main():
    with open('credit-large.txt') as f:
        n = int(f.readline())
        for k in xrange(n):
            total = int(f.readline().strip())
            f.readline()
            items = map(int, f.readline().strip().split(' '))
            print "Case #%s: %s" % (
                k+1,
                ' '.join(map(str, solve(total, items)))
            )


if __name__ == '__main__':
    main()