题解 P3985 【不开心的金明】

zengkaixin · 2018-11-16 20:53:01 · 题解

直接背包是会爆空间的，那么考虑压缩。记录所有物品的价格的最小值和最大值maxv和minv,当minv<=300的时候可以直接背包求解，另一种情况可以很容易由约束条件得到，w/minv == w/maxv，这样就可以直接贪心选取得到答案。

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 300*100 + 500;
const int maxint = 0x3f3f3f3f;
int dp[maxn];
int n,w;
struct node{
    int v, p;
};
node data[200];
struct cmp{
    bool operator ()(const node &a, const node &b){
        return a.p > b.p;
    }
};
int main(){
    int i,j;
    scanf("%d %d",&n, &w);
    int maxv = 0;
    int minv = maxint;
    for(i = 1; i <= n; i++) {
            scanf("%d %d",&data[i].v, &data[i].p);
            if(data[i].v > maxv) maxv = data[i].v;
            if(data[i].v < minv) minv = data[i].v;
    }
    sort(data + 1, data + n + 1, cmp());
    memset(dp, 0, sizeof(dp));
    if(minv <= 300){
        for(i = 1; i <= n; i++){
            for(j = maxn - 1; j >= data[i].v; j--){
                dp[j] = max(dp[j - data[i].v] + data[i].p, dp[j]);
            }
        }
        printf("%d\n", dp[w]);
    }else{
        int tn = w / minv;
        int ans = 0;
        for(i = 1; i <= tn ; i++) ans+=data[i].p;
        printf("%d\n",ans);
    }
    return 0;
}