【学习笔记】0/1背包不DP
2026-06-24 20:35:01
发布于：浙江
49阅读
0回复
0点赞
众所周知，0/1背包问题用的一般都是DP动态规划，但时间复杂度是O(n*k)，n和k稍微高一点就直接TLE了，而：
贪心算法的时间复杂度是O(n log n)，比DP动态规划快了非常多，但是不能保证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]}); // 输出三种策略的最大值
}
性能报告：
时间复杂度是 O(n log n)
空间复杂度是 O(n)
正确率>99%（不一定绝对正确）
有帮助，赞一个