题解 P3985 【不开心的金明】

· · 题解

这道题乍一看像一个裸的01背包，但是仔细看数据范围就会发现 数组根本放不下。 但是再读一遍题会发现好像有一个很明显的条件没有用： 妈妈看到购物单后进行了审查，要求购物单上所有的物品价格的极差（最贵的减去最便宜的）不超过3（当然金明至今不知道为什么会这样）

这样的话其实可以以300为分界线化为两部分来做。当最小值 <=300 时当一个背包做，>300 时贪心做；

这个相信楼上题解都提到过了，但为什么要这么分呢？

现在取所有价格里面最大为 maxn ，最小为 minn ；

首先，极差为3，我们假设买100件（最多件），那么现在都买最便宜的和都买最贵的差 3 100 元钱； 这个差值在 minn>300 时无论如何都买不成另一件了，也就是说，此时可以买的最大件数就是 w/maxn 。 那么买的件数 <100 时，买最便宜的和都买最贵的差值 < 3 100 元钱，和上一种情况一样； 此时按照p从大到小排序，从大往小选 w/maxn 件就是答案了；

但是当minn<=300时完全有可能再买一件，两件，更多件。件数不确定，只能按照01背包的思想DP做了；

代码如下

#include <iostream>
#include <cstdio> 
#include <algorithm>
using namespace std;

int p[102],v[102],n,w;
int f[300002],maxn,minn=9999999;
bool cmp(int x,int y){
    return x>y;
}
int main(){
    scanf("%d%d",&n,&w);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&v[i],&p[i]);
        minn=min(minn,v[i]);
        maxn=max(maxn,v[i]);
    }
    if(minn<=300){
        for(int i=1;i<=n;i++){
            for(int j=w;j>=v[i];j--){
                f[j]=max(f[j],f[j-v[i]]+p[i]);
            }
        }
        printf("%d",f[w]);
    }
    else{
        int ans=0;
        sort(p+1,p+n+1,cmp);
        for(int i=1;i<=w/maxn;i++)
            ans+=p[i];
        printf("%d",ans);
    }
    return 0;
}