UVA - 12325 Zombie's Treasure Chest （分类搜索）

题目：

有一个体积为N的箱子和两种数量无限的宝物。宝物1的体积为S1，价值为V1；宝物2的体积为S2，价值为V2.输入均为32位带符号整数。计算最多能装多大价值的宝物，每种宝物都必须拿非负整数个。

思路：

看完紫书的分析，不知道怎么判断N/S1、N/S2到底在那个范围内较大、较小，于是就用了下面的方法，不过这个方法效率低的很

S1个宝物2的体积=S2个宝物1的体积，他们的价值就是S1*V2和S2*V1.

1.如果S1*V2 > S2*V1,那么宝物1最多拿S2-1个，因为一旦满了S2个宝物1，这些就可以转换成S1个宝物2。然后枚举宝物1就可以了，注意这里范围是min{S2-1，N/S1}。

2.如果S1*V2 < S2*V1,那么宝物2最多拿S1-1个，因为一旦满了S1个宝物2，这些就可以转换成S2个宝物1。然后枚举宝物2就可以了，注意这里范围是min{S1-1，N/S2}。

3.如果S1*V2 = S2*V1,那么如果V1 > V2,就尽量多拿宝物1，相反就尽量多拿宝物2。

然后写代码就ok了。

代码：

#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define MAX 1000000009

#define FRE() freopen("in.txt","r",stdin)

#define FRO() freopen("out.txt","w",stdout)

using namespace std;

typedef long long ll;

const int maxn = ;

ll n,s1,v1,s2,v2;

int main(){

    //FRE();

    ios::sync_with_stdio(false);

    int T,kase=;

    cin>>T;

    while(T--){

        cin>>n>>s1>>v1>>s2>>v2;

        ll a = s1*v2, b= s2*v1;

        ll ans = ;

        if(a>b){//对应上述情况1

            for(ll i=; i<min(s2,n/s1+); i++){

                ll num = (n-i*s1)/s2;

                ans = max(ans,i*v1+num*v2);

            }

        }else if(a<b){//对应上述情况2

            for(ll i=; i<min(s1,n/s2+); i++){

                ll num = (n-i*s2)/s1;

                ans = max(ans,i*v2+num*v1);

            }

        }else{//情况3中按各个宝物价格大小决定枚举那个宝物

            if(v1>v2){

                ll i=;

                for(; i<(n/s1); i++){

                    ll num = (n-i*s1)/s2;

                    ans = max(ans, i*v1+num*v2);

                }

            }else {

                ll i=;

                for(; i<(n/s2); i++){

                    ll num = (n-i*s2)/s1;

                    ans = max(ans, i*v2+num*v1);

                }

            }

        }

        cout<<"Case #"<<++kase<<": "<<ans<<endl;

    }

    return ;

}

AC之后在VJ中发现了一个判断较大较小的方法做的，于是我又改了改自己写的代码，发现当这个界限设在1e3~1e4的时候，搜索的效率会达到最大。

当（N/S1）较小的时候，就枚举宝物1，尽量多拿宝物2，当（N/S2）较小的时候，就枚举宝物2，尽量多拿宝物1，如果两者都较小的时候，就按上边的1、2两个情况进行分析。

代码：

#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define MAX 1e3

#define FRE() freopen("in.txt","r",stdin)

#define FRO() freopen("out.txt","w",stdout)

using namespace std;

typedef long long ll;

const int maxn = ;

ll n, s1, v1, s2, v2;

int main() {

    //FRE();

    ios::sync_with_stdio(false);

    int T, kase = ;

    cin >> T;

    while(T--) {

        cin >> n >> s1 >> v1 >> s2 >> v2;

        ll c = n / s1, d = n / s2;

        ll a = s1 * v2, b = s2 * v1;

        ll ans = ;

        if(c < MAX) {

            for(ll i = ; i < (n / s1 + ); i++) {

                ll num = (n - i * s1) / s2;

                ans = max(ans, i * v1 + num * v2);

            }

        } else if(d < MAX) {

            for(ll i = ; i < (n / s2 + ); i++) {

                ll num = (n - i * s2) / s1;

                ans = max(ans, i * v2 + num * v1);

            }

        } else if(a > b) {

            for(ll i = ; i < min(s2, n / s1 + ); i++) {

                ll num = (n - i * s1) / s2;

                ans = max(ans, i * v1 + num * v2);

            }

        } else if(a <= b) {

            for(ll i = ; i < min(s1, n / s2 + ); i++) {

                ll num = (n - i * s2) / s1;

                ans = max(ans, i * v2 + num * v1);

            }

        }

        cout << "Case #" << ++kase << ": " << ans << endl;

    }

    return ;

}

巴特西

UVA - 12325 Zombie's Treasure Chest （分类搜索）

最新文章

热门文章