装载问题 回溯深搜法

2.装载问题

【问题描述】

       有一批共n个集装箱要装上艘载重量为c的轮船，其中集装箱i的重量为wi。找出一种最优装载方案，将轮船尽可能装满，即在装载体积不受限制的情况下，将尽可能重的集装箱装上轮船。

【输入格式】

       由文件load.in给出输入数据。第一行有2个正整数n和c。n是集装箱数，c是轮船的载重量。接下来的1行中有n个正整数，表示集装箱的重量。

【输出格式】

       将计算出的最大装载重量输出到文件load.out。

【输入样例】

5 10

7 2 6 5 4

【输出样例】

     10

 

 

       开始我想偏了，因为我才做完工作分配问题，觉得这道题也差不多，就写出了最初成品代码：

#include<bits/stdc++.h>
using namespace std;
int n,c,w[210],maxn=0;
bool vis[210];
void dfs(int,int);
int main()
{
	cin>>n>>c;
	for(int i=1;i<=n;i++)
		cin>>w[i];
	sort(w+1,w+n+1);
	dfs(1,0);
	cout<<maxn;
	return 0;
}
void dfs(int box,int sum)
{
	for(int j=n;j>=1;j--)
	{
		if(sum>c)
			return;
		if(!vis[j]&&(sum+w[j])<=c)
		{
			sum+=w[j];
			vis[j]=true;
			maxn=max(maxn,sum);
			dfs(box-1,sum);
			sum-=w[j];
			vis[j]=false;
		}
	}
}

       我把测试数据试了一下，对的，可我不放心（我做题老是只对测试数据其他都错的），又试了一组，超时了：

20 1000

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

       于是，我又打了几个补丁 ：

#include<bits/stdc++.h>
using namespace std;
int n,c,w[210],maxn=0,summ=0;
bool vis[210];
void dfs(int,int);
int main()
{
	cin>>n>>c;
	for(int i=1;i<=n;i++)
		cin>>w[i];
	sort(w+1,w+n+1);
	for(int i=1;i<=n;i++)
		summ+=w[i];
	if(summ<c)
	{
		cout<<summ;
		return 0;
	}
	dfs(1,0);
	cout<<maxn;
	return 0;
}
void dfs(int box,int sum)
{
	if(maxn==c)
		return;
	for(int j=n;j>=1;j--)
	{
		if(sum>c)
			return;
		if(!vis[j]&&(sum+w[j])<=c)
		{
			sum+=w[j];
			vis[j]=true;
			maxn=max(maxn,sum);
			dfs(box-1,sum);
			sum-=w[j];
			vis[j]=false;
		}
	}
}

       虽然后来测不出哪儿错了，但这毕竟是打补丁打出来的，怎么也放不了心，就换了一下思路（老师指引的）， 就是一组一组地试：

7+2+6   大于10了，maxn=9；

7+2+5   大于10了，maxn=9；

7+2+4   大于10了，maxn=9；

7+6       大于10了，maxn=9；

7+5       大于10了，maxn=9；

7+4       大于10了，maxn=9；

2+6+5   大于10了，maxn=9；

2+6+4   大于10了，maxn=9；

…………

6+4       没的拓展了，maxn=10；

…………

返回主程序，maxn=10。

      我很快写出了代码：

#include<bits/stdc++.h>
using namespace std;
int n,c,w[1010],sum=0,maxn=0;
void dfs(int);
int main()
{
	cin>>n>>c;
	for(int i=1;i<=n;i++)
		cin>>w[i];
	dfs(1);
	cout<<maxn;
	return 0;
}
void dfs(int i)
{
	for(int j=i;j<=n;j++)
		if(sum+w[j]<=c)
		{
			sum+=w[j];
			maxn=max(sum,maxn);
			dfs(j+1);
			sum-=w[j];
		}
}