嘎嘎嘎嘎嘎嘎
2025-12-21 13:01:56
发布于：上海
开始时间：2025/12/20 10:33
额几天时间还算是比较充裕的吧。
先安排一下做什么吧？
1.复习剪枝DFS
2.完成老师布置的课后作业
3.总结一下周一到周五的学习
*4.（附加项）完成5题6级题目
先复习昨天没有复习完（或者说刚开了个头）的剪枝DFS。
依旧装箱问题。
看一眼老师给的一个总结。
上周课程的主题是：【最优性剪枝】，知识点如下：
核心思想：当前代价已经 ≥ 已知最优答案 → 不可能更优 → 直接剪掉。
用途：解决最小值类搜索（TSP、小猫爬山、最短路径、装箱问题）。
要求：代价必须单调递增，往下走只会更差。
⭐ 重点
- 要有当前最优解作为“上界”（best）。
- 当前代价 >= best 就剪。
⭐ 难点
- 怎么尽早拿到一个上界（排序或贪心）。
- 怎么估计剩余最小代价（lower bound）。
⭐易错点
- 写成 > 而不是 >=。
- 忘记回溯导致判断错误。
感觉对这套逻辑还不是很熟悉，打算先去看看别的在前面的题目，有没有更容易理解的。
应该是这个链接描述
啊啊啊我突然想去做拿到我没做出来的记搜的紫色神奇题目欸。
两个人饲养了N只小猫，花钱让他们做索道下山。
索道上的缆车最大承重量是W，N只小猫的重量分别是C1,C2,CN。
当然，每辆缆车上的小猫的重量之和不能超过W。
一辆缆车一美元。
所以他们想知道，最少需要付多少美元才能使所有小猫都坐上缆车。
好像不难，也好理解。
那么直接开始搓代码吧！
琢磨了好长时间，然后超时了。
怎么会，我明明加优化了啊啊啊。
先放一下代码吧：
#include<bits/stdc++.h>
using namespace std;
int n,W;
const int N=20;
int c[N];
bool vis[N];
bool cmp(int a,int b){
return a>b;
}
int ans=INT_MAX;
void dfs(int x,int now,int v){
//现在已经有多少只小猫坐上缆车，现在的花费是多少，现在这辆缆车上的重量
if(now>=ans)return;
if(x==n+1){
if(v)now++;
ans=min(ans,now);
return;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
vis[i]=1;
if(c[i]==W-v)dfs(x+1,now+1,0);
else if(c[i]<W-v)dfs(x+1,now,v+c[i]);
else if(c[i]>W-v)dfs(x+1,now+1,c[i]);
vis[i]=0;
}
}
}
int main(){
cin>>n>>W;
for(int i=1;i<=n;i++)cin>>c[i];
sort(c+1,c+1+n,cmp);
dfs(1,0,0);
cout<<ans;
return 0;
}
那么如何进行进一步的优化呢？
1.使用排序/贪心尽早拿到一个上界
试试看吧。
额使用此神秘代码喜获37pts，剩下的从TLE变成了WA。
我研究一下。
#include<bits/stdc++.h>
using namespace std;
int n,W;
const int N=20;
int c[N];
bool vis[N];
bool cmp(int a,int b){
return a>b;
}
int ans=INT_MAX;
void dfs(int x,int now,int v){
//现在已经有多少只小猫坐上缆车，现在的花费是多少，现在这辆缆车上的重量
if(now>ans)return;
if(x==n+1){
if(v)now++;
ans=min(ans,now);
return;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
vis[i]=1;
if(c[i]==W-v)dfs(x+1,now+1,0);
else if(c[i]<W-v)dfs(x+1,now,v+c[i]);
else if(c[i]>W-v)dfs(x+1,now+1,c[i]);
}
}
}
bool vis1[N];
int main(){
cin>>n>>W;
for(int i=1;i<=n;i++)cin>>c[i];
//sort(c+1,c+1+n,cmp);
sort(c+1,c+1+n);
int suma=0;
for(int i=n;i>=1;i--){
if(vis1[i])continue;
int ax=lower_bound(c+1,c+1+n,W-c[i])-c;
int noww=c[i];
for(int j=1;j<=ax;j++){
if(noww+c[j]>W)break;
if(!vis1[j]){
vis1[j]=1;
noww+=c[j];
}
}
suma++;
}
ans=suma;
dfs(1,0,0);
cout<<ans;
return 0;
}
好烦，我改了好几版，都出问题。
怎么回事
关键是它还不是T，也没有测试数据可以下。
我燃尽了
就这样吧
看题解去了
好吧其实我打算再看看。
但是我真的觉得我求的最小值没什么问题啊。
为什么会错啊
欸等一下，是不是我的DFS错了？
好吧我DFS好像确实写错了。
我改改吧。
去吃饭。
去喝酸奶。
去睡觉。
3：30了 我c
继续写。
为什么会错啊啊啊啊.
我尽我所能。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll W;
const int N=20;
int c[N];
bool vis[N];
bool cmp(int a,int b){
return a>b;
}
ll ans=INT_MAX;
void dfs(int x,ll now,int v,ll y){
//现在已经有多少只小猫坐上缆车，现在的花费是多少，现在这辆缆车上的重量
//cout<<x<<" "<<now<<" "<<v<<" "<<y<<" "<<ans<<" "<<y/W<<endl;
if((now+(y/W))>ans)return;
if(x==n+1){
if(v)now++;
ans=min(ans,now);
return;
}
//cout<<11111<<endl;
for(int i=1;i<=n;i++){
//cout<<now+(y/W)<<endl;
if(now+(y/W)>ans)return;
//cout<<now+(y/W)<<endl;
if(!vis[i]){
vis[i]=1;
// cout<<11111<<endl;
if(now+(y/W)>ans)return;
if(c[i]==W-v)dfs(x+1,now+1,0,y-c[i]);
else if(c[i]<W-v)dfs(x+1,now,v+c[i],y-c[i]);
else if(c[i]>W-v)dfs(x+1,now+1,c[i],y-c[i]);
if((now+(y/W))>ans)return;
vis[i]=0;
}
}
}
bool vis1[N];
int main(){
cin>>n>>W;
for(int i=1;i<=n;i++)cin>>c[i];
//sort(c+1,c+1+n,cmp);
sort(c+1,c+1+n);
//for(int i=1;i<=n;i++)cout<<c[i]<<" ";
//cout<<endl;
int suma=0;
ll sum=0;
for(int i=1;i<=n;i++)sum+=c[i];
for(int i=n;i>=1;i--){
if(vis1[i])continue;
int ax=lower_bound(c+1,c+i,W-c[i])-c;
// cout<<i<<" "<<c[i]<<" "<<ax<<" "<<suma<<endl;
if(c[ax]>W-c[i])ax--;
int noww=c[i];
vis1[i]=1;
for(int j=1;j<=ax;j++){
if(noww+c[j]>W)break;
if(!vis1[j]){
// cout<<j<<" "<<c[j]<<endl;
vis1[j]=1;
noww+=c[j];
}
}
suma++;
}
//cout<<suma<<endl;
sort(c+1,c+1+n,cmp);
ans=suma;
dfs(1,0,0,sum);
cout<<ans;
return 0;
}
我去看题解。
算了。
我再想想。
我想不出来。
我去看题解。
我看完了。
大部分题解的思路是把猫塞进车里。
我觉得这种思路没什么问题。
但为什么我的思路就是错的。
为什么呢？
我想是因为。
我不知道。
我过了。
放一下代码吧：
#include<bits/stdc++.h>
using namespace std;
const int N=25;
int a[N];
int c[N];
int n,W;
int ans=INT_MAX;
void dfs(int x,int now){
if(now>ans)return;
if(x==n+1){
ans=min(ans,now);
return;
}
for(int i=1;i<=now;i++){
if(c[i]+a[x]<=W){
c[i]+=a[x];
dfs(x+1,now);
c[i]-=a[x];
}
}
c[now+1]=a[x];
dfs(x+1,now+1);
c[now+1]=0;
}
int main(){
cin>>n>>W;
for(int i=1;i<=n;i++)cin>>a[i];
dfs(1,1);
cout<<ans;
return 0;
}
额我讲一下吧，是这样的：
这道题就是一个非常典型的你的DFS构造会大大改变你的DFS树的形态和最终的运行时间。
我一开始的做法，思路非常不清楚。
大概的轮廓是，对于每一辆车，我都思考一下每一只猫能不能放进去。
放不进去，我就新开一辆出来。
那么，我不仅在DFS的过程中，暴力枚举了车的数量，我还没举了猫是如何放进去的。
其实就是有一种两种都枚举，思路非常不清楚的感觉，显得写题的人类是一个弱智。
所以就算做了再多的优化，它的本质超时会非常非常的严重。
暴力之间亦分上下的。
100pts的那个代码，它赢在了哪路呢？
看似都是一个循环的事儿，非常具有迷惑性。
但本质上就是不一样。
因为递归的次数是完全不一样的。
100的代码，它仅仅只是枚举了当前的这只猫放在哪里。
但是（最多）只有37的代码，在每次DFS里都枚举了每只猫的去向：
能塞进当前的车里的，就塞，然后下一轮。
不能塞进车里的，就新开一辆。
这种方法，不仅会导致已经在车里的猫被重复便利，还会导致
有一些情况需要很多次才能遍历到。
本质是非常非常暴力的。
我再想想怎么描述。我还是觉得描述的不清楚。
放猫的过程，有无数种可能，无数种形态，最初的解法，
就是把每一种形态每一种可能都过一遍。
这个可能的数量无限大。
那么思考，第一种和第二种的区别在哪里？
第一种，它的无限种可能在一开始就会全部都进行出来，导致时间复杂度爆炸。
额还是有点抽象。
这两个代码给我的感觉类似于这样：
一个很慌乱的做出了很多很多选择，然后大部分都是错的。
一个有条理地做出了精炼的选择，最后想正确答案步步逼近。
差不多了，不说这道题了，现在已经17:39了，再在这道题目上耗时间，我后面的事情很多来不及。
试试看这个链接描述
好像差不多欸。
双倍经验！
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int n,W;
int a[N];
int ans=INT_MAX;
int r[N];
void dfs(int x,int now){
if(now>=ans)return;
if(x==n+1){
ans=now;
return;
}
for(int i=1;i<=now;i++){
if(r[i]+a[x]<=W){
r[i]+=a[x];
dfs(x+1,now);
r[i]-=a[x];
}
}
r[now+1]=a[x];
dfs(x+1,now+1);
r[now+1]=0;
}
int main(){
cin>>n>>W;
for(int i=1;i<=n;i++)cin>>a[i];
dfs(1,0);
cout<<ans;
return 0;
}
啊下一题吧。
链接描述
这道题跟前面两题不太一样的。
没有“价值”一说，n<=30，如何进行优化？
啊不管了，先来一发暴力！
啊拿了40
情理之中，意料之内。
如何优化？
加了点东西，拿了60pts.
#include<bits/stdc++.h>
using namespace std;
const int N=40;
int a[N];
bool vis[N];
int W,n;
int ans=INT_MIN;
bool cmp(int a,int b){
return a>b;
}
void dfs(int x,int now,int ms,int b){
if(ans==W)return;
if(now+a[n]>W){
ans=max(ans,now);
return;
}
ans=max(ans,now);
for(int i=1;i<=n;i++){
if(!vis[i]&&now+a[i]<=W){
vis[i]=1;
if(i==b)dfs(x+1,now+a[i],a[b-1],b-1);
else dfs(x+1,now+a[i],ms,b);
vis[i]=0;
}
}
}
int main(){
cin>>W>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n,cmp);
dfs(1,0,a[n],n);
cout<<W-ans;
return 0;
}
但是接下来我真的不知道怎么优化了。
qwq给题目卖个萌
放过我吧球球了
我真不会优化。
但我会看题解。
没关系。
一切都会好起来的。
明天考试考不了第一怎么办？
月考有塌方怎么办？
……
再说吧。
去吃晚饭吧。
我懂了！
在进行DFS的时候，每次的x一般都直接作为下标。
而不是作为“进行了几次递归”的一个变量。
！
赋值语句要写在return前面。
过了，放个代码。
#include<bits/stdc++.h>
using namespace std;
int V,n;
const int N=35;
int a[N];
int ans=INT_MAX;
void dfs(int x,int now){
//cout<<x<<" "<<now<<endl;
ans=min(ans,now);
if(x==n+1)return;
//ans=min(ans,now);
if(now>=a[x])dfs(x+1,now-a[x]);
dfs(x+1,now);
}
int main(){
cin>>V>>n;
for(int i=1;i<=n;i++)cin>>a[i];
dfs(1,V);
cout<<ans;
return 0;
}
下一题。
链接描述
这道题跟最优性剪枝有什么关系吗？
试试看打一发暴力吧。
等等……我好像有思路了。
要注意有没有特殊可能。
额暴力打完了，拿了30pts。
我不太喜欢做剪枝。
真的。
放一下暴力代码
#include<bits/stdc++.h>
using namespace std;
int n,sum;
const int N=20;
const int M=12349;
int a[N][N];
int vis[M];
bool ans=0;
void dfs(int x){
if(ans)return;
// cout<<x<<endl;
for(int i=1;i<=a[x-1][1]-1;i++){
//cout<<i<<endl;
a[x][1]=i;
memset(vis,0,sizeof vis);
bool sum=1;
for(int j=1;j<=x-1;j++){
a[x][j+1]=a[x-1][j]-a[x][j];
if(a[x][j+1]<1){
sum=0;
break;
}
}
//if(sum)cout<<x<<endl;
//if(sum)for(int j=1;j<=x;j++)cout<<a[x][j]<<" ";
//if(sum)cout<<endl;
if(!sum)continue;
if(ans)return;
if(x!=n)dfs(x+1);
else if(!ans){
bool can=0;
for(int j=1;j<=n;j++){
vis[a[n][j]]++;
if(vis[a[n][j]]!=1||a[n][j]>12){
can=1;
break;
}
}
for(int i=1;i<=n;i++)if(vis[i]!=1)can=1;
if(!can)for(int j=1;j<=n;j++)cout<<a[n][j]<<" ";
if(!can)ans=1;
}
}
}
int main(){
cin>>n>>sum;
if(n==1){
cout<<sum;
return 0;
}
a[1][1]=sum;
dfs(2);
return 0;
}
等等……我觉得好像不是这么写的。
我改一下。
洛谷评测机炸了……玩我呢？
好吧。拿了80pts。但是我真的不太会优化……
依旧展示代码。
#include<bits/stdc++.h>
using namespace std;
int n,sum;
const int N=20;
int vis[N];
int d[N];
int s[N][N];
bool check(){
for(int i=1;i<=n;i++)s[n][i]=d[i];
for(int i=n-1;i>=1;i--){
for(int j=1;j<=i;j++){
s[i][j]=s[i+1][j]+s[i+1][j+1];
}
}
if(s[1][1]==sum)return 1;
else return 0;
}
bool ans=0;
void dfs(int x){
if(ans)return;
if(x==n+1){
if(check()&&!ans){
for(int i=1;i<=n;i++)cout<<d[i]<<" ";
ans=1;
}
return;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
vis[i]=1;
d[x]=i;
dfs(x+1);
vis[i]=0;
}
}
}
int main(){
cin>>n>>sum;
dfs(1);
return 0;
}
有帮助，赞一个