首页 > 代码库 > swust oj 简单背包问题(0032) DFS
swust oj 简单背包问题(0032) DFS
Description
设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…wn。
问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S。
如果有满足条件的选择，则此背包有解，否则此背包问题无解。
Input
输入数据有多行，包括放入的物品重量为s，物品的件数n，以及每件物品的重量（输入数据均为正整数）
多组测试数据。
Output
对于每个测试实例，若满足条件则输出“YES”，若不满足则输出“NO“
Sample Input
20 5
1 3 5 7 9
Sample Output
YES
AC代码：
1 #include<stdio.h> 2 int AC,w[1000];//AC来标记和是否为s； 3 void DFS(int k,int s)//搜索 4 { 5 int i; 6 for(i=0;i<2;i++){//i=0表示不用背包w[k],i=1表示用背包w[k] 7 int sum=0;//用来记录是否用了背包 8 sum+=w[k]*i; 9 if(sum>s)//是否超重，如果超重，就不要这个背包10 sum=0;11 if(sum==s)//记录正确结果12 AC=1;13 return;14 }15 if(sum<s&&k>=0)//当背包质量小于s时，s-sum表示s中sum的质量已占16 DFS(k-1,s-sum);//继续搜索17 if(AC==1)18 return;19 }20 return;21 }22 int main()23 {24 int i,n,s;25 26 while(scanf("%d%d",&s,&n)!=EOF){27 AC=0;28 for(i=0;i<n;i++)29 scanf("%d",&w[i]);30 DFS(n-1,s);31 if(AC==1)32 printf("YES\n");33 else34 printf("NO\n");35 }36 return 0;37 }
结束语：
确实觉得自己BFS DFS很糟糕，不过多练一下，应该能ok。
swust oj 简单背包问题(0032) DFS
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。