算法课(6)

算法报告六 装载问题

                                                               16122020   钟顺源

一、题目大意

将n个体积分别为wi集装箱放置在容量分别为c1,c2的轮船中,问是否能有个合理放置的方案,若有,则输出字典序最大的方案。

二、分析

题目可以转换为有n个元素,对于某个元素,有取或不取两个操作,取的集装箱总体积不超过c1,不取的集装箱总体积不超过c2,取或不取的问题可以dp做,爆搜当然也可以,但既然学到的搜索,就爆搜+减枝
因为要记录最佳的方案情况,而更新一次最佳方案需要$O(n)$的复杂度搜索每一种方案需要$O(2^n)$,所以总的复杂度是$O(n×2^n)$的复杂度,那如何将复杂度降为$O(2^n)$?
做加法不做乘法
先找出第一艘船能装的满足条件的最多货物,之后在按先搜1再搜0的顺序搜索第一个满足条件的组合,因为是按1,0的顺序搜索的,所以第一个满足条件的方案一定是字典序最大的。
简单来说就是 两次dfs。

三、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
const int N=30;
int a[N],b[N];
int bestw=0;//
int n; int c1,c2;
int all;
int fac[N],pre[N];
int cnt=0;
set<string> ans;
void dfs1(int pos,int sum){
if(pos==n+1) {
bestw=max(bestw,sum);
return ;
}
if(sum + fac[pos] < bestw) return ;
if(sum + a[pos] <= c1)
dfs1(pos+1,sum+a[pos]);
if(pre[pos] - sum <= c2)
dfs1(pos+1,sum);
}
void dfs2(int pos,int sum,string xx){
if(pos==n+1) {
if(bestw==sum) ans.insert(xx);
return ;
}
if(sum + fac[pos] < bestw) return ;
if(sum + a[pos] <= c1)
dfs2(pos+1,sum+a[pos],xx+'1');
if(ans.size()) return ;
if(pre[pos] - sum <= c2)
dfs2(pos+1,sum,xx+'0');
}
int main()
{
int cas=0;
freopen("SOU_input.txt","r",stdin);
freopen("SOU_output.txt","w",stdout);
while(~scanf("%d",&n)){
all=0;pre[0] = 0;
cnt=0;
ans.clear();
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
all+=a[i];
pre[i] = all;
}
fac[n+1] = 0;
for(int i=n;i>=1;i--) fac[i] = fac[i+1] + a[i];
scanf("%d%d",&c1,&c2);
printf("Case %d\n",++cas);
bestw=-1;
dfs1(1,0);
dfs2(1,0,"");
if(bestw==-1) {puts("No");continue;}
cout<<bestw<<" ";
auto v=ans.begin();
cout<<*v<<endl;
}
return 0;
}

四、体会

    这次实验还是蛮有意思的,之前一直没有考虑到更新的答案的开销如何消除,但没想到只要先处理出答案,在去搜字典序最大的路径就可以了,两个dfs的复杂度都是$O(2^n)$,所以最后的总的复杂度也是$O(2^n)$。

-------------本文结束-------------