UVA12325题：宝箱（暴力求解）

题目

传送门：https://vjudge.net/problem/UVA-12325

这次介绍一个稍微看起来没有特别多技术含量的题目，叫做宝箱。

这个场景是这样子滴，首先，我们有一个背包，放在我们面前有无限多的两种宝藏，第一种体积为s1价值为v1,第二种体积为s2价值为v2,我们必须想出一种拿宝物的策略使得在我们有限背包内装的宝藏价值最大。

我们分析下这个问题，如果一种宝藏的体积非常大，我们枚举的个数就会非常少，情况就会变少，所以我们这么暴力求解就可以提高效率。

那么，如果两者的以及都非常小呢，那我们通过思考，可以得出这么一个规律，当两者的体积都很小时，我们分别对s1×v2与s2×v1进行计算，假设我们算出了s1×v2>s2×v1,那么我们可以得到说价值为v1的宝物的个数绝对不会超过（s2-1），为什么呢？因为一旦价值为v1的宝物我们拿了s2个，那我们完全可以把s2个价值v1的宝物兑换成总价值更高的s1个价值为v2的宝物。所以通过以上论证我们就可以得出暴力枚举的上限。

代码

#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn=60000;

long long max(long long a,long long b){
    return a>b?a:b;
}

long long sol(ll n,ll s1,ll v1,ll s2,ll v2){
    if(s1<s2){
        swap(s1,s2);
        swap(v1,v2);
    }
    long long ans=0;
    if(n/s1>maxn){
        for(long long i=0; i<=s1; i++)
            ans=max(ans,v2*i+(n-i*s2)/s1*v1);
        for(long long i=0; i<=s2; i++)
            ans=max(ans,v1*i+(n-i*s1)/s2*v2);
        return ans;
    }
    else{
        for(ll i=0;i*s1<=n;i++)
            ans=max(ans,v1*i+(n-i*s1)/s2*v2);
        return ans;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    while(cin>>T){
        for(int cas=1;cas<=T;cas++){
            ll n,s1,v1,s2,v2;
            cin>>n>>s1>>v1>>s2>>v2;
            cout <<"Case #"<<cas<<": "<< sol(n,s1,v1,s2,v2) <<endl;
        }
    }
    return 0;
}