首页 > 代码库 > SWUST OJ 0032 简单的背包 解题报告
SWUST OJ 0032 简单的背包 解题报告
Description
输入数据有多行，包括放入的物品重量为s，物品的件数n，以及每件物品的重量（输入数据均为正整数）
多组测试数据。
Input
对于每个测试实例，若满足条件则输出“YES”，若不满足则输出“NO“
Output
20 5
1 3 5 7 9
View Code
Sample Input
YES
解体思路：贪心不行，，直接上搜索。。。
1 #include<stdio.h> 2 int w[100],s,n,x,book[100]; 3 void dfs(int weight) 4 { 5 int i; 6 if(weight==s)x++; 7 if(weight>s)return ; 8 for(i=1;i<=n;i++) 9 {10 if(book[i]==0)11 {12 book[i]=1;13 dfs(weight+w[i]);14 book[i]=0;15 }16 }17 }18 int main()19 {20 int i;21 while(scanf("%d %d",&s,&n)!=EOF)22 {23 for(i=1;i<=n;i++)24 {25 scanf("%d",&w[i]);26 }27 dfs(0);28 if(x>0)printf("YES\n");29 else printf("NO\n");30 x=0;31 }32 return 0;33 }
SWUST OJ 0032 简单的背包 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。