c824: 第六題:背包問題 EX

c824: 第六題:背包問題 EX

題 意:
現 在 有 一 個 容 量 為 2M 的 背 包,以 及 N 個 重 量 為 2a 價 值 為 b 的 物 品,求 最 大 價 值。
M109N106a109

solve:
看 似 是 背 包 問 題,實 際 上 是 簡 單 的 貪 心。
把 兩 個 重 量 相 同 且 小 於 2M 的 物 品 合 併,變 成 重 2a+1, 價 值 bi+bj 的 物 品。
直 到 所 有 物 品 都 變 成 重 2M 為 止。
如 果 找 不 到 相 同 的 但 是 重 量 還 是 小 於 2M 的 話,可 以 想 像 有 一 個 重2a, 價 值 0 的 物 品,與 之 進 行 合 併,因 為 價 值 為 0 所 以 並 不 影 響 結 果。

code:

留言

熱門文章