谁看看问题在哪？？在线等

题目很简单，第一行是输入营养的数量N,第二行为N种的营养的需求量，第三行为可供选择的M种组合，以下M行每行是N种营养在该种是的具体含量。
求可以满足所需要求的最少所用的组合数及所选的组合序号。
我用DFS做的，但不知为什么在search()中的else{}中，执行完for循环后不执行if语句。
我先在VS2005中用C++写的，但在调试时就是不执行if语句，后改成在VC6.0中用C也不行，还请达人赐请。


下面是一组测试数据
4
100 200 300 400
3
50   50  50  50
200 300 200 300
900 150 389 399

#include<stdio.h>




int arr[15][25];
int tar[25],temp[15];

int n,m,sum,end;
int tag=0;
void search(int max)
{
int i;
tag=0;
if(max<n)
{
search(max+1);

for(i=0;i<m;i++)
tar[i]-=arr[max][i];
sum++;
temp[end++]=max+1;


search(max+1);

for(i=0;i<m;i++)
tar[i]+=arr[max][i];
sum--;
end--;
}
else
{
printf("%d\n",100);
for(i=0;i<m;i++)
{
if(tar[i]>0)
tag=1;
}
if(0==tag)
return;
                     //问题就在这




}

}





int main()
{
int i,j;



scanf("%d",&m);
for(i=0;i<m;i++)
{

scanf("%d",&tar[i]);

}


scanf("%d",&n);
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{


scanf("%d",&arr[i][j]);
}
}


search(0);



  
printf("%d\n",sum);
return 0;
}

13 个解决方案

#1

忘记删了，for前面的printf("%d\n",100); 没有用。

#2

//你应该定义一个局部变量tag.
//放在全局,貌似逻辑不对.
printf("%d\n",100); 
for(i=0;i <m;i++) 
{ 
if(tar[i]>0) 
tag=1; 
} 
if(0==tag) 
return;

 

#3

引用 2 楼 baihacker 的回复:

C/C++ code//你应该定义一个局部变量tag.//放在全局,貌似逻辑不对.printf("%d\n",100);for(i=0;i<m;i++) 
{if(tar[i]>0) 
tag=1; 
}if(0==tag)return;

和这个没关吧

#4

//关键在于,在进入这里的时候,tag的状态.你这里printf一下,用个小数据测试一下.
printf("%d\n",100); 
for(i=0;i <m;i++) 
{ 
if(tar[i]>0) 
tag=1; 
} 

#5

楼主
执行完for循环后有执行if语句啊
怎么没有啊
因为你用了递归
return后只是从里层的search里返回

#6

看看先

#7

mark  看看  貌似

引用 5 楼 xiaoQ008 的回复:

楼主 
执行完for循环后有执行if语句啊 
怎么没有啊 
因为你用了递归 
return后只是从里层的search里返回 

#8

引用 5 楼 xiaoQ008 的回复:

楼主
执行完for循环后有执行if语句啊
怎么没有啊
因为你用了递归
return后只是从里层的search里返回

果然是这样的，但要怎样才能执行到if(0==tag)return; 这句直接从函数中退出来呢。

#9

引用 5 楼 xiaoQ008 的回复:

楼主
执行完for循环后有执行if语句啊
怎么没有啊
因为你用了递归
return后只是从里层的search里返回

是了

#10

我用DFS做的，但不知为什么在search()中的else{}中，执行完for循环后不执行if语句。 

for(i=0;i <m;i++) 
{ 
if(tar[i]>0) 
tag=1; 
} 
if(0==tag) {printf("%d\n",100); 
return; }
把你原来的printf改到这里来,执行了三次
貌似和你的问题描述得不一样.
难道是我理解错了
4
100 200 300 400
3
50  50  50  50
200 300 200 300
900 150 389 399
100
100
100
0

#11

引用 10 楼 baihacker 的回复:

我用DFS做的，但不知为什么在search()中的else{}中，执行完for循环后不执行if语句。

C/C++ codefor(i=0;i<m;i++) 
{if(tar[i]>0) 
tag=1; 
}if(0==tag) {printf("%d\n",100);return; }
把你原来的printf改到这里来,执行了三次
貌似和你的问题描述得不一样.
难道是我理解错了41002003004003505050502003002003009001503893991001001000

是我搞错了，确实执行了，但我的想法是执行return 后从search()返回到main()中，但其只从下一级的search()返回到了上一层的search(),不知道有什么办法可以直接返回到main()中。

#12

int solved = 0;//是否已经解决
void search(int max) 
{ 
int i; 
tag=0; 
if(max <n) 
{ 
search(max+1); //返回后,如果solved为1则直接return

for(i=0;i <m;i++) 
tar[i]-=arr[max][i]; 
sum++; 
temp[end++]=max+1; 


search(max+1); //返回后,如果solved为1则直接return


for(i=0;i <m;i++) 
tar[i]+=arr[max][i]; 
sum--; 
end--; 
} 
else 
{ 
printf("%d\n",100); 
for(i=0;i <m;i++) 
{ 
if(tar[i]>0) 
tag=1; 
} 
if(0==tag) 
return; 




} 

} 

#13

恩，这样可以，我怎么没想到呢。