文章
20
粉丝
147
获赞
13
访问
51.7k
knap( s, n) =
︳true, s= 0
︳false, s< 0
︳false, s> 0 且n<0
︳knap( s, n- 1) 或knap(s- Wn, n- 1) , s> 0 且n>= 1;
代码如下:
# include<stdio.h>
# include<string.h>
int date[1005];
int f(int w, int s)
{
if(w == 0) return 1;//正好
if(w<0 || w>0 && s == 0) return 0;
if(f(w - date[s], s - 1)) return 1;//退出来再选下一个
return f(w, s - 1);//选择下一个
}
int main()
{
int i, Weight, n;
while(scanf("%d %d", &Weight, &n) != EOF)
{
memset(date,0, sizeof(date));
for(i = 1; i <= n; i++)
scanf("%d",&date[i]);
if(f(Weight, n))
printf("yes!\n");
else printf("no!\n");
}
return 0;
}
代码总结:
a. 跳出条件需要构思好,应该以总重量为核心,而不是每个物品的重量;
b. 返回条件需要构思好;
c. 注意逻辑的表达:
if(w<0 || w>0 && s == 0) return 0; 正确
if(w>0 || w<0 && s == 0) return 0; 错误
if(s==0) return 0; if(w>0 || w<0) return 0; 错误
登录后发布评论
暂无评论,来抢沙发