• 题意:给定$n$组数,每组数包含2个数字$S\_i$和$F\_i$。 要求:取其中几组数,要求他们的和最大,并且所有$S\_i$的和与$F\_i$的和均大于0。
  • $1\\leq N\\leq 400$ $-1000\\leq S\_i,F\_i\\leq 1000$
    • *
  • 可以看出,每组数有选与不选两种情况,可以转化为01背包,让$S\_i$作为物品体积,$F\_i$作为物品价值。但是由题意可以发现,$S\_i$有可能为负数,又因为$-1000\\leq S\_i\leq 1000$,所以背包体积可以是$-400000\\leq m\\leq 400000$,因为数组下标不可以为负,所以将整个数组向右平移$400000$个单位,把$400000$当做$0$。
  • 这样如果$S_i<0$那么正序枚举,反之倒序枚举。

代码:

    #include<bits/stdc++.h>
    using namespace std;

    int v[409],w[409];
    int f[800009],n;

    int main(){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>w[i]>>v[i];
        }
        memset(f,~0x3f,sizeof(f));
        f[400000]=0;
        for(int i=1;i<=n;i++){
            if(v[i]>=0){
                for(int j=800000;j>=v[i];j--){
                    f[j]=max(f[j],f[j-v[i]]+w[i]);
                }
            }
            else{
                for(int j=0;j<=800000+v[i];j++){
                    f[j]=max(f[j],f[j-v[i]]+w[i]);
                }
            }
        }
        int ans=0;
        for(int i=400000;i<=800000;i++) if(f[i]>=0) ans=max(ans,f[i]+i-400000);
        cout<<ans;
        return 0;
    }
Last modification:March 14th, 2020 at 08:49 pm