【学习笔记】0/1背包不DP

AC君

2026-05-16 08:42:03

发布于：浙江

18阅读

0回复

0点赞

众所周知，0/1背包问题用的一般都是DP动态规划，但时间复杂度是O(n*k)，n和k稍微高一点就直接TLE了，而：
贪心算法的时间复杂度是O(n log n)，比DP动态规划快了1000多倍，但是不能保证AC，我们就可以把几种贪心算法（排序方法）结合起来，提高容错率，下面是我写的一个小小的结合体：

#include <bits/stdc++.h>
using namespace std;
// 指令速度优化
#pragma GCC optimize("Ofast", "unroll-loops", "no-stack-protector", "fast-math")
#pragma GCC target("avx2", "avx512f", "avx512vl", "fma", "bmi2", "popcnt")
#pragma GCC diagnostic ignored "-Wunused-function"

struct p{ // 结构体定义
    long long a,b;
};
bool cmp1(const p &a, const p &b){ // 策略一：按性价比 从大到小 排序
    if(a.a==0||b.a==0)return a.a==0; // 如果a.a是0，直接返回
    return a.b*b.a>b.b*a.a; // 用叉乘 计算 性价比（不会受浮点数精度影响）并比较返回
}
bool cmp2(const p &a, const p &b){ // 策略二：按时间 从小到大 排序
    if(a.a!=b.a)return a.a<b.a; // 如果a,b时间不相等，正常比较返回
    return a.b>b.b; // 否则看价值，比较返回
}
bool cmp3(const p &a, const p &b){ // 策略三：按价值 从小到大 排序
    if(a.b!=b.b)return a.b>b.b; // 如果a,b价值不相等，正常比较返回
    return a.a<b.a; // 否则看时间，比较返回
}
int main(){
    ios::sync_with_stdio(false); // 必备速度提升
    cin.tie(0);
    long long n,k,res[4]={0},cnt[4]={0}; // 十年OI一场空，不开long long见祖宗
    cin>>n>>k;
    vector<p> a(n+1); // 只存一份真实数据
    vector<int> idx2(n+1),idx3(n+1); // 只存下标，内存占用极小
    for(int i=1;i<=n;i++){
        cin>>a[i].a>>a[i].b;
        idx2[i]=i;
        idx3[i]=i;
    }
    sort(a.begin()+1,a.end(),cmp1);
    sort(idx2.begin()+1,idx2.end(),[&a](int i,int j){return cmp2(a[i],a[j]);});
    sort(idx3.begin()+1,idx3.end(),[&a](int i,int j){return cmp3(a[i],a[j]);});

    // 贪心遍历时通过下标访问
    for(int i=1;i<=n;i++){
        if(res[1]+a[i].a<=k){res[1]+=a[i].a;cnt[1]+=a[i].b;}
        if(res[2]+a[idx2[i]].a<=k){res[2]+=a[idx2[i]].a;cnt[2]+=a[idx2[i]].b;}
        if(res[3]+a[idx3[i]].a<=k){res[3]+=a[idx3[i]].a;cnt[3]+=a[idx3[i]].b;}
    }
    cout<<max({cnt[1],cnt[2],cnt[3]}); // 输出三种策略的最大值
}