uva12325 ZombiesTreasureChest

出處 ： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3747

解題策略

暴力法

解法一

S1*S2=S2*S1佔有相同空間，若V2取S1個的總價值(V2*S1) 大於 V1取S2個的總價值(V1*S2)，

V1物品一定會在S2-1個以下，若V1有S2個會用V2的S1個取代，價值更高。

若V2取S1個的總價值(V2*S1) 小於 V1取S2個的總價值(V1*S2)， V2物品一定會在S1-1個以下，若V2有S1個會用V1的S2個取代，價值更高。

解法二

N/S1<10000 直接列舉第1種物品，就可以決定第2種物品求最大值。

N/S2<10000 直接列舉第2種物品，就可以決定第1種物品求最大值。

若N很大，而S1與S2都很小，不適用上述方法，改用以下方法，

S1*S2=S2*S1佔有相同空間，若V2取S1個的總價值(V2*S1) 大於 V1取S2個的總價值(V1*S2)，

V1物品一定會在S2-1個以下，若V1有S2個會用V2的S1個取代，價值更高。

若V2取S1個的總價值(V2*S1) 小於 V1取S2個的總價值(V1*S2)， V2物品一定會在S1-1個以下，若V2有S1個會用V1的S2個取代，價值更高。