C/C++教程

走进“深度搜索基础训练“,踏入c++算法殿堂(二)

本文主要是介绍走进“深度搜索基础训练“,踏入c++算法殿堂(二),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

小航做起了第二道题……

1076. 【搜索与回溯算法】装载问题 (Standard IO)

时间限制: 1000 ms 空间限制: 262144 KB 具体限制

题目描述:

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

输入:

第一行有2个正整数n和c。n是集装箱数,c是轮船的载重量。接下来的1行中有n个正整数,表示集装箱的重量。

输出:

将计算出的最大装载重量输出

样例输入:

5 10
7 2 6 5 4

样例输出:

10

数据范围限制:

n<=35,c<=1000

“其实这就是一道超级简单的背包问题,可以用递归解决。”小航想,“建立一个临时重量和最终重量,搜索每一个数字(选与不选),只要搜索后的结果大于最终结果,就赋值。”

#include<iostream>
using namespace std;
int n,c,w[40],s;
void dfs(int x,int sx)//第x个物品,sx为临时重量
{
	if(x>n)
	{
		if(sx>s) s=sx;//赋值
		return;
	}
	else
	{
		if(sx+w[x]<=c)//如果装入此物品,还没超载的话……
		{
			dfs(x+1,sx+w[x]);//装入此物品,并搜索下一件物品
		}
		dfs(x+1,sx);//在不装入此物品的情况下,搜索下一件物品
	}
}
int main()
{
	cin>>n>>c;
	for(int i=1;i<=n;i++) cin>>w[i];
	dfs(1,0);
	cout<<s;//输出最终重量
}

       但是。小航后来知道,这个看似简单的程序险些超时。他不甘心,修改了一下:

#include<bits/stdc++.h>
using namespace std;
int n,c,w[40],s,b[40],ms=0;
void dg(int x)
{
	if(s>=c)
	{
		if(s==c)
		{
			printf("%d",s);
			exit(0);
		}
		s-=w[x-1];
		if(ms<s)
			ms=s;
		s+=w[x-1];
	}
	else if(x==n)
	{
		if(ms<s)
			ms=s;
	}
	else
	{
		s+=w[x];
		dg(x+1);
		s-=w[x];
		dg(x+1);
	}
	return;
}
int main()
{
	scanf("%d%d",&n,&c);
	for(int i=0;i<n;i++)
		scanf("%d",&w[i]);
	dg(0);
	printf("%d",ms);
	return 0;
} 

        这样运行时间缩短了不少,复杂度是n的……

        之后,下一题又映入眼帘……

这篇关于走进“深度搜索基础训练“,踏入c++算法殿堂(二)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!