PAST1I - NISHIO Hirokazu's Scrapbox (Auto-translated from Japanese)

PAST1I

I - Parts Procurement

https://gyazo.com/c2448c08a7e7e39a1cf0cef3c676a36a

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

code:python

def solve(N, M, SS, CS):

INF = 9223372036854775807

table = INF * (2 ** N)

table0 = 0

SS = int(s.replace("Y", "1").replace("N", "0"), 2) for s in SS

for i in range(M):

s = SSi

for src in range(2 ** N):

dst = s | src

tabledst = min(tabledst, tablesrc + CSi)

ret = table2 ** N - 1

if ret == INF:

return -1

return ret

bit DP

Cost minimization

First Algorithm Practical Skills Test

---

This page is auto-translated from /nishio/PAST1I. 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.