c824: 第六題：背包問題 EX
c824: 第六題：背包問題 EX
題 意:
現 在 有 一 個 容 量 為 $2^M$ 的 背 包，以 及 $N$ 個 重 量 為 $2^a$ 價 值 為 $b$ 的 物 品，求 最 大 價 值。
$M \leq 10^9$、$N \leq 10^6$、$a \leq 10^9$
solve:
看 似 是 背 包 問 題，實 際 上 是 簡 單 的 貪 心。
把 兩 個 重 量 相 同 且 小 於 $2^M$ 的 物 品 合 併，變 成 重 $2^{a+1}$, 價 值 $b_i + b_j$ 的 物 品。
直 到 所 有 物 品 都 變 成 重 $2^M$ 為 止。
如 果 找 不 到 相 同 的 但 是 重 量 還 是 小 於 $2^M$ 的 話，可 以 想 像 有 一 個 重$2^a$, 價 值 $0$ 的 物 品，與 之 進 行 合 併，因 為 價 值 為 0 所 以 並 不 影 響 結 果。
code:
$M \leq 10^9$、$N \leq 10^6$、$a \leq 10^9$
solve:
看 似 是 背 包 問 題，實 際 上 是 簡 單 的 貪 心。
把 兩 個 重 量 相 同 且 小 於 $2^M$ 的 物 品 合 併，變 成 重 $2^{a+1}$, 價 值 $b_i + b_j$ 的 物 品。
直 到 所 有 物 品 都 變 成 重 $2^M$ 為 止。
如 果 找 不 到 相 同 的 但 是 重 量 還 是 小 於 $2^M$ 的 話，可 以 想 像 有 一 個 重$2^a$, 價 值 $0$ 的 物 品，與 之 進 行 合 併，因 為 價 值 為 0 所 以 並 不 影 響 結 果。
code:
留言
張貼留言