Оптимизатсияи битсет

Оптимизатсияи битсет

Идея

std::bitset (ё битсети худатон дар uint64_t) ба мо имкон медиҳад, ки бисёр ҳолатҳои булевиро дар як амалиёт коркард кунем.

Ба ҷои навсозии DP / гузаришҳо як ҳуҷайра-як ҳуҷайра, мо 64 битро якбора навсозӣ мекунем (ё андозаи дигари блоки калимаи мошин), бинобар ин омили доимӣ хеле беҳтар мешавад.

Ин хеле муфид аст, вақте ки:

• ҳолати DP булевӣ аст (дастрас / дастнорас)
• гузаришҳоро метавон бо shift / OR / AND ифода кард
• маҳдудиятҳо он қадар калонанд, ки доимиҳо аҳамият доранд

Мисол 1

Масъала

$N$ ашё дода шудааст. Ашёи $i$ вазни $w_i$ дорад. Санҷед, ки оё зермаҷмӯае ҳаст, ки вазни умумияш маҳз $W$ бошад.

DP-и классикӣ

Бигзор d[j] = 1 агар суммаи дастрас бошад.