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