I - Parts Procurement

  • image
  • Thoughts.
    • The problem of matching 10 parts with minimum cost by choosing some from a set of 1000 parts.
    • 2^1000 is too big, but 1000 x 2^10 is about 10^6, so there is plenty of room
    • DP with the 2^10 subset as the definition domain and the minimum cost to achieve it as the value domain.
    • Initialize the empty set with 0 and others with INF and chmin for each set
  • Official Explanation OK
  • AC python
def solve(N, M, SS, CS):
    INF = 9223372036854775807
    table = [INF] * (2 ** N)
    table[0] = 0
    SS = [int(s.replace("Y", "1").replace("N", "0"), 2) for s in SS]
    for i in range(M):
        s = SS[i]
        for src in range(2 ** N):
            dst = s | src
            table[dst] = min(table[dst], table[src] + CS[i])
    ret = table[2 ** N - 1]
    if ret == INF:
        return -1
    return ret

This page is auto-translated from /nishio/PAST1I using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.