【学习笔记】0/1背包不DP
2026-05-16 08:42:03
发布于:浙江
众所周知,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]}); // 输出三种策略的最大值
}
性能报告:
时间复杂度是 O(n log n)
空间复杂度是 O(n)
正确率>99%(不一定绝对正确)
全部评论 1
这是啥,sale pro max?
昨天 来自 广东
0建议放到CSP-S2026
昨天 来自 广东
0神马玩意?
昨天 来自 浙江
0






















有帮助,赞一个