762
poj 1853 Cat
题意比较不是那么容易理解，题意：本题要求把一堆物品分成两堆，两堆总重量相差不到百分之2，即把物品进行背包，试着能否构成sum／（1 ＋ 1.02）到sum/(1 + 1.02) * 1.02之间的一个数。分析：背包搜索，当要从若干个物品中选出一些的时候，每次递归最好不要单纯地枚举第i个物品是要还是不要，而是要用一个循环从上一个要的物品开始去枚举下一个物品要第几个。
#include<stdio.h>
#include<string.h>
const int MAXN=102;
double rock[MAXN],sum;
bool vis[MAXN];
int n;
bool dfs(double l,double r,int a)
{
for(int i=a;i<n;i++)
{
if (rock[i]>=l && rock[i]<=r)
{
vis[i]=true;
return true;
}
else if(rock[i]<l)
{
vis[i]=true;
if (dfs(l-rock[i],r-rock[i],i+1)!=false)
return true;
}
vis[i] =false;
}
return false;
}
int main()
{
int i,j;
while(scanf("%d",&n) && n!=0)
{
sum=0;
for(i=0;i<n;i++)
{
scanf("%lf",&rock[i]);
sum+=rock[i];
}
memset(vis,0,sizeof(vis));
//核心的dfs
dfs(sum/2.02,sum*1.02/2.02,0);
//输出
int i=0;
while(vis[i]==0)
i++;
printf("%d",i+1);
for(j=i+1;j<n;j++)
if(vis[j]!=0)
printf(" %d",j+1);
printf("\n");
}
return 0;
}
最后更新：2017-04-03 05:39:27