題目：Zombie's Treasure Chest

題意：有一個體積為N的箱子和兩種數量無限的寶物。 寶物1的體積為S1，價值為V1；寶物2的體積為S2，價值為V2。你的任務是計算最多能裝多大價值的寶物。

思路：分倆種情況枚舉：

枚舉1：當s1或s2的體積很大（即n/s1  n/s2 很小）時，枚舉較大體積的那個寶物即可。

枚舉2：當s1和s2的體積很小，但N又很大時，此時按枚舉1來就超時了，由題可得：S2個寶物1和S1個寶物2的體積相等，而價值分別為S2*V1和S1*V2。所以當前者較大時，寶物2最多s1-1個，因為以上的條件可知，當體積相等的條件下寶物1的價值大，所以寶物2不能再超出那個范圍了，這樣寶物1就不能放到最大化，總價值就不是最大化。后者較大時同理。 所以將倆種寶物都枚舉后取最大的。

參考：入門經典-例7-11-P210 + 紫書代碼庫

代碼：

#include <iostream>#include <cstdio>using namespace std;typedef long long ll;const int maxn = 65536;inline ll fun(ll tal,ll n,ll s1,ll s2,ll v1,ll v2){    ll ans = 0;    for(ll i=0;i<=n;i++) ans = max(ans,i*v2 + (tal-s2*i)/s1 * v1);return ans;}int main(){    ll T,n,s1,s2,v1,v2,ans,kcase = 1;    scanf("%lld",&T);    while(T--){        scanf("%lld%lld%lld%lld%lld",&n,&s1,&v1,&s2,&v2);        if( s1 > s2) swap(s1,s2),swap(v1,v2);//s2作為較大的        if((double)n / s2 > maxn) ans = max(fun(n,s1,s1,s2,v1,v2),fun(n,s2,s2,s1,v2,v1));//倆個都很小        else ans = fun(n,n/s2,s1,s2,v1,v2);//        PRintf("Case #%lld: %lld/n",kcase++,ans);    }    return 0;}