小航做起了第二道题……
【搜索与回溯算法】装载问题 (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的……。
之后，下一题又映入眼帘……
