5 / 5 Classic DP Families

When W Is Enormous

Two exact knapsack tables are available. The weight table is O(nW)O(nW): best value at each capacity. The value table is O(n∑vi)O(n \sum v_i): minimum weight reaching each total value, after which you read off the largest value whose minimum weight is at most WW.

instance nn WW max viv_i
A 100 10510^5 10910^9
B 100 10910^9 10310^3
C 10510^5 10510^5 10910^9

Which of these can be solved exactly within roughly 10810^8 elementary operations? More than one applies.

A

C, by the value table: ∑vi≤1014\sum v_i \le 10^{14}.

B

A, by the weight table: 100×105=107100 \times 10^5 = 10^7 updates.

C

B, by the value table: ∑vi≤105\sum v_i \le 10^5, so 100×105=107100 \times 10^5 = 10^7 updates.

D

C, by the weight table: 105×105=101010^5 \times 10^5 = 10^{10} updates.