鏈接：https://ac.nowcoder.com/acm/contest/24872/I
來源：牛客網(wǎng)

題目描述

從n個元素中選任意個組成兩個集合元素總體積（數(shù)值）相等的集合，求所有可能集合的元素價值之和的最大值。

額外條件為可以將最多k個數(shù)變?yōu)樵瓉淼?倍以有機會于構(gòu)造更多元素組成的集合獲得更大價值。

注意到為多過程多決策問題，且決策過程復(fù)雜，因此應(yīng)該考慮動態(tài)規(guī)劃

設(shè)f[i][j][k]:從前i個物品選，總體積定義為（大于base為左集合元素總體積大于右集合，小于則反之），且使用k次翻倍數(shù)值的機會所獲收益的最大值，則max{f[n][base][i]}(0=<i<=k)為最大收益。

注意到這里體積定義方法為雙方向選擇背包體積dp相關(guān)問題的經(jīng)典思維：定義為相對差值，而不是開兩個維度分別記錄所選數(shù)值，否則會超時且容易爆空間。