当01背包学会变形术
2024-09-19 19:31:27
发布于：浙江
本文拥有Macw07,アイドル(作者曰：致敬传奇排位出题王)，SJZ08和AC君的点赞，含金量极高，确定不来看看吗？
-1.在这篇文章之前
01背包，相信大家都会（不会请自学）。
然而，在アイドル的排位赛中，总有那么几道01背包，在模板上加一些奇妙的东西使其变得非常不可读
所以，饱受火星背包折磨的我，将做出此文，为抵抗01变式做出贡献
0.前置知识
01背包，众所周知，不会就去上网学
1.最初的起点——01背包模板
01背包第一形态：模板形态
【背包】01背包(优化)
题目描述
一个旅行者有一个最多能装 C 的背包，现在有 n 件物品，它们的重量分别是 它们的价值分别为每件物品都可以选择装入背包或者不装入，求旅行者能获得最大总价值。
输入格式
第 1 行：两个整数，C (背包容量，0 < C ≤ 30000) 和 N (物品数量，0 < N ≤ 10000)；
第 2~N+1行：每行二个整数 ，表示每个物品的重量和价值。
输出格式
仅一行，一个数，表示最大总价值。
样例 #1
样例输入 #1
10 4
2 1
3 3
4 5
7 9
样例输出 #1
12
经典01背包，当然要套最经典的模板
复杂度也是经典的O(nm)
code:
#include <bits/stdc++.h>
using namespace std;
struct bao{
int w,v;//w:strong v:coin
}a[30011];
long long dp[33333];
int main(){
int n,m;
cin>>m>>n;
for (int i=0;i<n;++i){
cin>>a[i].w>>a[i].v;
}
for (int i=0;i<n;++i){
for (int j=m;j>=a[i].w;--j){
dp[j]=max(dp[j-a[i].w]+a[i].v,dp[j]);
}
}
printf("%d",dp[m]);
return 0;
}
2.当n开始变小的时候
当n开始变小的时候，就说明你要做火星背包全家桶了
火星背包I
01背包第二形态：n小余极形态
这题观察到我们的都特别大，显然最终的时间复杂度肯定只能带n了
咋办？？
不急，是时候掏出黑科技——折半搜索了（选学，因为我也不懂）
时间复杂度为
code:
#include <bits/stdc++.h>
using namespace std;
const long long INF=1e18;
struct node{
long long w,v,id;
}pa[1<<20];
bool cmp(node a,node b){
return a.w<b.w;
}
node a[41];
int main(){
int n;
long long m;
cin>>n>>m;
for (int i=0;i<n;++i){
cin>>a[i].w>>a[i].v;
}
int n2=n/2;
for (int i=0;i<(1<<n2);++i){
long long nw=0,nv=0;
for (int j=0;j<n2;++j){
if (i >> j & 1){
nw+=a[j].w;
nv+=a[j].v;
}
}
pa[i]={nw,nv,i};
}
sort(pa,pa+(1<<n2),cmp);
//for(int i=0;i<1<<n2;++i){
// cout<<"AA "<<pa[i].w<<" "<<pa[i].v<<" "<<pa[i].id<<endl;
//}
int cnt = 1;
for(int i=1;i<1<<n2;++i){
if (pa[i].w==pa[cnt-1].w){
if (pa[i].v>pa[cnt-1].v){
pa[cnt-1] = pa[i];
}
}else if (pa[i].v>pa[cnt-1].v){
cnt+=1;
pa[cnt-1] = pa[i];
}
}
long long ans=0,sums=0;
int ans_1,ans_2;
for (int i=0;i<(1<<(n-n2));++i){
long long nw=0,nv=0;
for (int j=0;j<(n-n2);++j){
if (i >> j & 1){
nw+=a[j+n2].w;
nv+=a[j+n2].v;
}
}
if (nw<=m){
int pos=upper_bound(pa,pa+cnt,(node){m-nw,0,0},cmp)-pa;
//cout<<nw<<endl;
//for (int i=0;i<sum;++i){
//cout<<"{"<<pa[i].first<<","<<pa[i].second<<"}"<<" ";
//}
//cout<<endl;
pos -= 1;
if (ans<nv+pa[pos].v){
ans=nv+pa[pos].v;
ans_1=pa[pos].id;
ans_2=i;
}
//ans=max(ans,nv+pa[pos].second);
//co.push_back({i,pos});
//cout<<ans<<endl;
}
}
//cout<<ans_1<<" "<<ans_2<<endl;
vector<int> ansid;
for (int i=0;i<n2;++i){
if (ans_1 & (1<<i)){
ansid.push_back(i+1);
}
}
for (int i=0;i<(n-n2);++i){
if (ans_2 & (1<<i)){
ansid.push_back(i+1+n2);
}
}
cout<<ans<<" "<<ansid.size()<<endl;
for (int i=0;i<ansid.size();++i){
cout<<ansid[i]<<" ";
}
return 0;
}
01背包第三形态：火星式逆转形态
这题一看n和都小，其余的我们承受不住。所以显然时间复杂度显然只能带n和。
不妨想一下，你n和都小，我们是不是可以反过来，直接枚举最后的答案然后判断答案是否可行呢？
这么一思索，脑子里便能瞬间变出一个dp[i]呢（dp[i]指在想让最后价值变为i时的最小重量）
在思索一下，是不是dp[0]=0呢
这边界和公式都有了,接下来就交给代码了
时间复杂度为,最大1e8,勉强卡常过去
code
#include <bits/stdc++.h>
using namespace std;
int n,m,w[1111],v[1111],sum,ans=-1;
long long f[111111];
int main(){
cin>>n>>m;
for (int i=0;i<=100010;++i){
f[i]=1e13;
}
f[0]=0;
for (int i=1;i<=n;++i){
cin>>w[i]>>v[i];
sum+=v[i];
}
for (int i=1;i<=n;++i){
for (int j=sum;j>=1;--j){
f[j]=min(f[j],f[j-v[i]]+w[i]);
}
}
for (int i=sum;i>=0;--i){
if (f[i]<=m){
cout<<i<<endl;
return 0;
}
}
return 0;
}
3.当n开始变大的时候
01背包第4形态：多重01形态
显然，你就要去写一些思维题了
这道题比较有价值，建议思考一下再看题解
题解：
1.直觉
你在刚看到这题的反应估计是：这不 01 背包模板题吗，为啥会在绿题？
于是，你就高高兴兴的把 01 背包的模板修改了一下，放了上去。
结果就会这样 。
也是在这时，你看到了数据：
。
所以说，这题用传统 01 背包的 还真做不出来。
然而正在你苦苦思索时，你一看 和 的数据。
。
2.思路
和 这么小，所有男家丁的状态最多只有 多种， 又很大，肯定会有重复的情况，于是我们就可以定义一个二维数组 来保存当前状态的男家丁有多少个，这样子我们就得到了一个多重背包问题。
2.1二进制优化
然而普通多重背包的时间复杂度是 ，显然是会超时间的。所以说还得用到二进制优化，把时间复杂度优化为 。
:这里的 最大为 ， 最多为 ， (背包个数) 顶多也就 多一点点地样子，开个O2时间勉强能卡过。
：
#include <bits/stdc++.h>
using namespace std;
int dp[110000],w[100001],v[100001],s[1001][1001],we[100001],ve[100001];
int main(){
int n,m,k,t=0;
cin>>n>>m>>k;
for (int i=0;i<n;++i){
int we1,ve1;
cin>>we1>>ve1;
we[i]=we1;
ve[i]=ve1;
s[we[i]][ve[i]]+=1;
}
//二进制优化
for (int i=0;i<n;++i){
for (int j=1;j<=s[we[i]][ve[i]];j*=2){
w[t]=we[i]*j;
v[t]=j*ve[i];
s[we[i]][ve[i]]-=j;
t++;
}
if (s[we[i]][ve[i]]>0){
w[t]=s[we[i]][ve[i]]*we[i];
v[t]=s[we[i]][ve[i]]*ve[i];
t++;
s[we[i]][ve[i]]=0;
}
}
//01背包
for (int i=0;i<t;++i){
for (int j=m;j>=w[i];--j){
dp[j]=max(dp[j-w[i]]+v[i],dp[j]);
}
}
if (dp[m]<k){
cout<<"no"<<endl;
}else{
cout<<"yes"<<endl;
}
cout<<dp[m];
return 0;
}
//抄袭可耻！！！
4.探寻本质
看了这么多题目，相信你也发现了：
1.01变式最重要的就是挑软柿子捏，找到小的数据，根据这个想出对应的思路
2.没有小数据的背包一般都不在考背包
所以，“山重水复疑无路，柳暗花明又一村”，只要它还是背包，就一定是有一个比较简单的解的（火星背包I除外）。
5.结语
看到这里的，请按照以下操作进行：
1.@AC君：精选置顶
2.其他：点赞，评论（发个ding都行）
byebye~
有帮助，赞一个